CSES - Collecting Numbers II | Thu thập số II - LQDOJ: Le Quy Don Online Judge

CSES - Collecting Numbers II | Thu thập số II

Tác giả:

Flower_On_Stone , HoaiAnDeepTry , nguyendangquocthinh

Dạng bài

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một mảng mà chứa mỗi số giữa $1\ldots n$ chính xác một lần. Nhiệm vụ của bạn là thu thập các số từ $14 đến $n$ theo thứ tự tăng dần.

Trong mỗi vòng, bạn đi qua mảng từ trái sang phải và thu thập nhiều số nhất có thể.

Cho $m$ thao tác hoán đổi hai số trong mảng, nhiệm vụ của bạn là báo cáo số lượng vòng sau mỗi thao tác.

Input

Dòng đầu tiên có hai số nguyên $n$ và $m$: kích thước mảng và số lượng phép toán.
Dòng tiếp theo có $n$ số nguyên $x_1,x_2,\ldots,x_n$: các số trong mảng.
Cuối cùng, có $m$ dòng mô tả các thao tác. Mỗi dòng có hai số nguyên $a$ và $b$: các số tại vị trí $a$ và $b$ được hoán đổi.

Output

In $m$ số nguyên: số lượng vòng sau mỗi lần hoán đổi.

Constraints

$1 \le n,m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Sample input

Sample output

2
3
4

Bình luận

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int n,m; cin>>n>>m;
    int l = 1;
    int ind[n+2] = {0}, a[n+1] = {0};
    ind[n+1] = n+1;
    for (int i = 1; i <= n; i++) {
        int x; cin>>x;
        ind[x] = i;
        a[i] = x;
    }
    int c = 1;
    for (int i = 1; i <= n; i++) {
        if (l > ind[i]) 
        c++;
        l = ind[i];
    }
    while(m--) {
        int x,y; cin>>x>>y;
        int r = a[x], s = a[y];
        swap(a[x], a[y]);
        if (ind[r-1] <= ind[r] && ind[r-1] > y) c++;
        if (ind[r-1] > ind[r] && ind[r-1] <= y) c--;
        if (ind[r] <= ind[r+1] && y > ind[r+1]) c++;
        if (ind[r] > ind[r+1] && y <= ind[r+1]) c--;        
        ind[r] = y;
        if (ind[s-1] <= ind[s] && ind[s-1] > x) c++;
        if (ind[s-1] > ind[s] && ind[s-1] <= x) c--;
        if (ind[s] <= ind[s+1] && x > ind[s+1]) c++;
        if (ind[s] > ind[s+1] && x <= ind[s+1]) c--;    
        ind[s] = x;
        cout<<c<<endl;
    }
}

https://github.com/mrsac7/CSES-Solutions/blob/master/src/2217%20-%20Collecting%20Numbers%20II.cpp

Phản hồi

dbthuan208 • 9:44 p.m. 14 Tháng 6, 2023 •

bạn chỉnh lại đi sai chỗ $14 kìa phải là $1$

2
Phản hồi Chia sẻ