oj.uz

Submission #937050

# Submission time Handle Problem Language Result Execution time Memory
937050 2024-03-03T09:59:40 Z azberjibiou Seats (IOI18_seats) C++17
100 / 100
 1847 ms 119640 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1001000;
const int mxM=200100;
const int mxK=61;
const int MOD=1e9;
const ll INF=1e18;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
typedef struct lazyseg{
    pii seg[4*mxN]={};
    int lazy[4*mxN]={};
    pii mrg(pii a, pii b){
        if(a.fi!=b.fi) return max(a, b);
        return pii(a.fi, a.se+b.se);
    }
    void init(int idx, int s, int e){
        seg[idx]=pii(0, e-s+1);
        if(s==e) return;
        int mid=(s+e)/2;
        init(2*idx, s, mid);
        init(2*idx+1, mid+1, e);
    }
    void propagate(int idx){
        seg[2*idx].fi+=lazy[idx];
        seg[2*idx+1].fi+=lazy[idx];
        lazy[2*idx]+=lazy[idx];
        lazy[2*idx+1]+=lazy[idx];
        lazy[idx]=0;
    }
    void upd(int idx, int s1, int e1, int s2, int e2, int x){
        if(s2>e1 || s1>e2) return;
        if(s2<=s1 && e1<=e2){
            seg[idx].fi+=x, lazy[idx]+=x;
            return;
        }
        propagate(idx);
        int mid=(s1+e1)/2;
        upd(2*idx, s1, mid, s2, e2, x);
        upd(2*idx+1, mid+1, e1, s2, e2, x);
        seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
    }
}lazyseg;
int H, W, Q;
vector <vector <int>> v;
bool Chk[mxN];
pii pos[mxN];
pii qry[mxN];
lazyseg T1;
int S[mxN];
void input(){
    cin >> H >> W >> Q;
    v.resize(H);
    for(int i=0;i<H;i++) v[i].resize(W);
    for(int i=0;i<H*W;i++){
        int a, b;
        cin >> a >> b;
        v[a][b]=i;
        pos[i]=pii(a, b);
    }
    for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}

bool not_ok(int a, int b){
    return (a<0 || a>=H || b<0 || b>=W);
}
void add(int a, int rev, bool init){
    auto [ax, ay]=pos[a];
    for(int i=0;i<4;i++){
        int nx1=ax+dx[i], ny1=ay+dy[i], nx2=ax+dx[(i+1)%4], ny2=ay+dy[(i+1)%4];
        int val1, val2;
        if(not_ok(nx1, ny1)) val1=H*W;
        else val1=v[nx1][ny1];
        if(not_ok(nx2, ny2)) val2=H*W;
        else val2=v[nx2][ny2];
        if(a<val1 && a<val2){
            if(!init) T1.upd(1, 0, H*W-1, a, min(val1, val2)-1, -rev);
            else S[a]-=rev, S[min(val1, val2)]+=rev;
        }
        if(a>val1 && a>val2) {
            if(!init) T1.upd(1, 0, H*W-1, max(val1, val2), a-1, -rev);
            else S[max(val1, val2)]-=rev, S[a]+=rev;
        }
    }
}
void add_area(int a, bool rev){ //rev가 true면 제거하는 것
    int flag=(rev ? -1 : 1);
    auto [ax, ay]=pos[a];
    if(Chk[a]==rev) Chk[a]=(!rev), add(a, flag, false);
    for(int i=0;i<4;i++){
        if(not_ok(ax+dx[i], ay+dy[i])) continue;
        int av=v[ax+dx[i]][ay+dy[i]];
        if(Chk[av]==rev) Chk[av]=(!rev), add(av, flag, false);
    }
}
void init(){
    T1.init(1, 0, H*W-1);
    for(int i=0;i<H*W;i++){
        add(i, 1, true);
        Chk[i]=true;
    }
    for(int i=0;i<H*W;i++){
        if(i!=0) S[i]+=S[i-1];
        T1.upd(1, 0, H*W-1, i, i, S[i]);
    }
}
int swap_seats(int a, int b){
    add_area(a, true), add_area(b, true);
    auto [ax, ay]=pos[a];
    auto [bx, by]=pos[b];
    swap(v[ax][ay], v[bx][by]);
    swap(pos[a], pos[b]);
    add_area(a, false), add_area(b, false);
    return (T1.seg[1].fi==-4 ? T1.seg[1].se : 0);
}
void give_initial_chart(int h, int w, vector <int> r, vector <int> c){
    H=h, W=w;
    v.resize(H);
    for(int i=0;i<H;i++) v[i].resize(W);
    for(int i=0;i<H*W;i++){
        v[r[i]][c[i]]=i;
        pos[i]=pii(r[i], c[i]);
    }
    init();
}
/*
int main()
{
    gibon
    input();
    init();
    for(int i=1;i<=Q;i++) cout << swap_seats(qry[i].fi, qry[i].se) << '\n';
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4696 KB Output is correct
2 Correct 21 ms 4668 KB Output is correct
3 Correct 35 ms 4680 KB Output is correct
4 Correct 19 ms 4552 KB Output is correct
5 Correct 17 ms 4700 KB Output is correct
6 Correct 29 ms 4720 KB Output is correct
7 Correct 31 ms 4700 KB Output is correct
8 Correct 26 ms 4688 KB Output is correct
9 Correct 26 ms 4700 KB Output is correct
10 Correct 30 ms 4932 KB Output is correct
11 Correct 28 ms 4700 KB Output is correct
12 Correct 18 ms 4700 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4696 KB Output is correct
2 Correct 21 ms 4668 KB Output is correct
3 Correct 35 ms 4680 KB Output is correct
4 Correct 19 ms 4552 KB Output is correct
5 Correct 17 ms 4700 KB Output is correct
6 Correct 29 ms 4720 KB Output is correct
7 Correct 31 ms 4700 KB Output is correct
8 Correct 26 ms 4688 KB Output is correct
9 Correct 26 ms 4700 KB Output is correct
10 Correct 30 ms 4932 KB Output is correct
11 Correct 28 ms 4700 KB Output is correct
12 Correct 18 ms 4700 KB Output is correct
13 Correct 70 ms 4956 KB Output is correct
14 Correct 81 ms 4956 KB Output is correct
15 Correct 41 ms 4956 KB Output is correct
16 Correct 32 ms 5468 KB Output is correct
17 Correct 55 ms 4952 KB Output is correct
18 Correct 53 ms 5132 KB Output is correct
19 Correct 50 ms 4956 KB Output is correct
20 Correct 42 ms 5212 KB Output is correct
21 Correct 32 ms 4956 KB Output is correct
22 Correct 32 ms 5464 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 68920 KB Output is correct
2 Correct 483 ms 69064 KB Output is correct
3 Correct 466 ms 68948 KB Output is correct
4 Correct 463 ms 68872 KB Output is correct
5 Correct 479 ms 68868 KB Output is correct
6 Correct 451 ms 68872 KB Output is correct
7 Correct 496 ms 68856 KB Output is correct
8 Correct 501 ms 68876 KB Output is correct
9 Correct 457 ms 68868 KB Output is correct
10 Correct 461 ms 68804 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4956 KB Output is correct
2 Correct 98 ms 12628 KB Output is correct
3 Correct 465 ms 68924 KB Output is correct
4 Correct 576 ms 69144 KB Output is correct
5 Correct 427 ms 68692 KB Output is correct
6 Correct 808 ms 119640 KB Output is correct
7 Correct 474 ms 69012 KB Output is correct
8 Correct 469 ms 69304 KB Output is correct
9 Correct 462 ms 69200 KB Output is correct
10 Correct 469 ms 72016 KB Output is correct
11 Correct 459 ms 92192 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6052 KB Output is correct
2 Correct 90 ms 6072 KB Output is correct
3 Correct 169 ms 5908 KB Output is correct
4 Correct 223 ms 6352 KB Output is correct
5 Correct 368 ms 6616 KB Output is correct
6 Correct 854 ms 69676 KB Output is correct
7 Correct 884 ms 69664 KB Output is correct
8 Correct 849 ms 69456 KB Output is correct
9 Correct 1116 ms 69456 KB Output is correct
10 Correct 803 ms 69456 KB Output is correct
11 Correct 918 ms 69532 KB Output is correct
12 Correct 834 ms 69436 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4696 KB Output is correct
2 Correct 21 ms 4668 KB Output is correct
3 Correct 35 ms 4680 KB Output is correct
4 Correct 19 ms 4552 KB Output is correct
5 Correct 17 ms 4700 KB Output is correct
6 Correct 29 ms 4720 KB Output is correct
7 Correct 31 ms 4700 KB Output is correct
8 Correct 26 ms 4688 KB Output is correct
9 Correct 26 ms 4700 KB Output is correct
10 Correct 30 ms 4932 KB Output is correct
11 Correct 28 ms 4700 KB Output is correct
12 Correct 18 ms 4700 KB Output is correct
13 Correct 70 ms 4956 KB Output is correct
14 Correct 81 ms 4956 KB Output is correct
15 Correct 41 ms 4956 KB Output is correct
16 Correct 32 ms 5468 KB Output is correct
17 Correct 55 ms 4952 KB Output is correct
18 Correct 53 ms 5132 KB Output is correct
19 Correct 50 ms 4956 KB Output is correct
20 Correct 42 ms 5212 KB Output is correct
21 Correct 32 ms 4956 KB Output is correct
22 Correct 32 ms 5464 KB Output is correct
23 Correct 588 ms 68920 KB Output is correct
24 Correct 483 ms 69064 KB Output is correct
25 Correct 466 ms 68948 KB Output is correct
26 Correct 463 ms 68872 KB Output is correct
27 Correct 479 ms 68868 KB Output is correct
28 Correct 451 ms 68872 KB Output is correct
29 Correct 496 ms 68856 KB Output is correct
30 Correct 501 ms 68876 KB Output is correct
31 Correct 457 ms 68868 KB Output is correct
32 Correct 461 ms 68804 KB Output is correct
33 Correct 68 ms 4956 KB Output is correct
34 Correct 98 ms 12628 KB Output is correct
35 Correct 465 ms 68924 KB Output is correct
36 Correct 576 ms 69144 KB Output is correct
37 Correct 427 ms 68692 KB Output is correct
38 Correct 808 ms 119640 KB Output is correct
39 Correct 474 ms 69012 KB Output is correct
40 Correct 469 ms 69304 KB Output is correct
41 Correct 462 ms 69200 KB Output is correct
42 Correct 469 ms 72016 KB Output is correct
43 Correct 459 ms 92192 KB Output is correct
44 Correct 29 ms 6052 KB Output is correct
45 Correct 90 ms 6072 KB Output is correct
46 Correct 169 ms 5908 KB Output is correct
47 Correct 223 ms 6352 KB Output is correct
48 Correct 368 ms 6616 KB Output is correct
49 Correct 854 ms 69676 KB Output is correct
50 Correct 884 ms 69664 KB Output is correct
51 Correct 849 ms 69456 KB Output is correct
52 Correct 1116 ms 69456 KB Output is correct
53 Correct 803 ms 69456 KB Output is correct
54 Correct 918 ms 69532 KB Output is correct
55 Correct 834 ms 69436 KB Output is correct
56 Correct 118 ms 6004 KB Output is correct
57 Correct 338 ms 6140 KB Output is correct
58 Correct 500 ms 6644 KB Output is correct
59 Correct 1316 ms 69560 KB Output is correct
60 Correct 1847 ms 69456 KB Output is correct
61 Correct 1131 ms 69552 KB Output is correct
62 Correct 1034 ms 69716 KB Output is correct
63 Correct 1581 ms 69548 KB Output is correct
64 Correct 1291 ms 69716 KB Output is correct
65 Correct 1185 ms 69616 KB Output is correct
66 Correct 1293 ms 69708 KB Output is correct
67 Correct 1274 ms 64384 KB Output is correct
68 Correct 1033 ms 75336 KB Output is correct
69 Correct 1714 ms 84592 KB Output is correct