oj.uz

답안 #937047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937047 2024-03-03T09:49:29 Z azberjibiou 자리 배치 (IOI18_seats) C++17
100 / 100
 3396 ms 210772 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]={};
    map <pii, int> mp;
    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]);
    }
    void add(int s, int e, int x){
        mp[pii(s, e)]+=x;
    }
    void flush(int s, int e){
        for(auto [a, b] : mp){
            if(b!=0) upd(1, s, e, a.fi, a.se, b);
        }
        mp.clear();
    }
}lazyseg;
int H, W, Q;
vector <vector <int>> v;
bool Chk[mxN];
pii pos[mxN];
pii qry[mxN];
lazyseg T1;
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){
    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) T1.add(a, min(val1, val2)-1, -rev);
        //T1.upd(1, 0, H*W-1, a, min(val1, val2)-1, -rev);
        if(a>val1 && a>val2) T1.add(max(val1, val2), a-1, -rev);
        //T1.upd(1, 0, H*W-1, max(val1, val2), a-1, -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);
    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);
    }
}
void init(){
    T1.init(1, 0, H*W-1);
    for(int i=0;i<H*W;i++){
        add(i, 1);
        Chk[i]=true;
    }
}
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);
    T1.flush(0, H*W-1);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 50004 KB Output is correct
2 Correct 30 ms 50012 KB Output is correct
3 Correct 38 ms 49984 KB Output is correct
4 Correct 21 ms 50000 KB Output is correct
5 Correct 17 ms 50012 KB Output is correct
6 Correct 34 ms 49960 KB Output is correct
7 Correct 34 ms 50000 KB Output is correct
8 Correct 40 ms 50004 KB Output is correct
9 Correct 33 ms 50004 KB Output is correct
10 Correct 35 ms 49864 KB Output is correct
11 Correct 32 ms 50004 KB Output is correct
12 Correct 18 ms 50012 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 50004 KB Output is correct
2 Correct 30 ms 50012 KB Output is correct
3 Correct 38 ms 49984 KB Output is correct
4 Correct 21 ms 50000 KB Output is correct
5 Correct 17 ms 50012 KB Output is correct
6 Correct 34 ms 49960 KB Output is correct
7 Correct 34 ms 50000 KB Output is correct
8 Correct 40 ms 50004 KB Output is correct
9 Correct 33 ms 50004 KB Output is correct
10 Correct 35 ms 49864 KB Output is correct
11 Correct 32 ms 50004 KB Output is correct
12 Correct 18 ms 50012 KB Output is correct
13 Correct 59 ms 50780 KB Output is correct
14 Correct 68 ms 51036 KB Output is correct
15 Correct 34 ms 50880 KB Output is correct
16 Correct 27 ms 51292 KB Output is correct
17 Correct 50 ms 51036 KB Output is correct
18 Correct 51 ms 51036 KB Output is correct
19 Correct 47 ms 50788 KB Output is correct
20 Correct 42 ms 51292 KB Output is correct
21 Correct 28 ms 50780 KB Output is correct
22 Correct 28 ms 51292 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2612 ms 192136 KB Output is correct
2 Correct 983 ms 184156 KB Output is correct
3 Correct 726 ms 156084 KB Output is correct
4 Correct 799 ms 187472 KB Output is correct
5 Correct 822 ms 177624 KB Output is correct
6 Correct 834 ms 156164 KB Output is correct
7 Correct 703 ms 156388 KB Output is correct
8 Correct 883 ms 156488 KB Output is correct
9 Correct 863 ms 187472 KB Output is correct
10 Correct 763 ms 176968 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 50780 KB Output is correct
2 Correct 124 ms 59984 KB Output is correct
3 Correct 812 ms 183696 KB Output is correct
4 Correct 2524 ms 192436 KB Output is correct
5 Correct 791 ms 156080 KB Output is correct
6 Correct 1338 ms 206856 KB Output is correct
7 Correct 967 ms 183912 KB Output is correct
8 Correct 804 ms 177748 KB Output is correct
9 Correct 757 ms 156468 KB Output is correct
10 Correct 837 ms 184096 KB Output is correct
11 Correct 938 ms 210772 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 51408 KB Output is correct
2 Correct 94 ms 51404 KB Output is correct
3 Correct 111 ms 51408 KB Output is correct
4 Correct 143 ms 51532 KB Output is correct
5 Correct 206 ms 52052 KB Output is correct
6 Correct 1000 ms 157036 KB Output is correct
7 Correct 1022 ms 157012 KB Output is correct
8 Correct 1006 ms 156976 KB Output is correct
9 Correct 1421 ms 157012 KB Output is correct
10 Correct 1006 ms 156840 KB Output is correct
11 Correct 876 ms 157276 KB Output is correct
12 Correct 943 ms 156848 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 50004 KB Output is correct
2 Correct 30 ms 50012 KB Output is correct
3 Correct 38 ms 49984 KB Output is correct
4 Correct 21 ms 50000 KB Output is correct
5 Correct 17 ms 50012 KB Output is correct
6 Correct 34 ms 49960 KB Output is correct
7 Correct 34 ms 50000 KB Output is correct
8 Correct 40 ms 50004 KB Output is correct
9 Correct 33 ms 50004 KB Output is correct
10 Correct 35 ms 49864 KB Output is correct
11 Correct 32 ms 50004 KB Output is correct
12 Correct 18 ms 50012 KB Output is correct
13 Correct 59 ms 50780 KB Output is correct
14 Correct 68 ms 51036 KB Output is correct
15 Correct 34 ms 50880 KB Output is correct
16 Correct 27 ms 51292 KB Output is correct
17 Correct 50 ms 51036 KB Output is correct
18 Correct 51 ms 51036 KB Output is correct
19 Correct 47 ms 50788 KB Output is correct
20 Correct 42 ms 51292 KB Output is correct
21 Correct 28 ms 50780 KB Output is correct
22 Correct 28 ms 51292 KB Output is correct
23 Correct 2612 ms 192136 KB Output is correct
24 Correct 983 ms 184156 KB Output is correct
25 Correct 726 ms 156084 KB Output is correct
26 Correct 799 ms 187472 KB Output is correct
27 Correct 822 ms 177624 KB Output is correct
28 Correct 834 ms 156164 KB Output is correct
29 Correct 703 ms 156388 KB Output is correct
30 Correct 883 ms 156488 KB Output is correct
31 Correct 863 ms 187472 KB Output is correct
32 Correct 763 ms 176968 KB Output is correct
33 Correct 61 ms 50780 KB Output is correct
34 Correct 124 ms 59984 KB Output is correct
35 Correct 812 ms 183696 KB Output is correct
36 Correct 2524 ms 192436 KB Output is correct
37 Correct 791 ms 156080 KB Output is correct
38 Correct 1338 ms 206856 KB Output is correct
39 Correct 967 ms 183912 KB Output is correct
40 Correct 804 ms 177748 KB Output is correct
41 Correct 757 ms 156468 KB Output is correct
42 Correct 837 ms 184096 KB Output is correct
43 Correct 938 ms 210772 KB Output is correct
44 Correct 48 ms 51408 KB Output is correct
45 Correct 94 ms 51404 KB Output is correct
46 Correct 111 ms 51408 KB Output is correct
47 Correct 143 ms 51532 KB Output is correct
48 Correct 206 ms 52052 KB Output is correct
49 Correct 1000 ms 157036 KB Output is correct
50 Correct 1022 ms 157012 KB Output is correct
51 Correct 1006 ms 156976 KB Output is correct
52 Correct 1421 ms 157012 KB Output is correct
53 Correct 1006 ms 156840 KB Output is correct
54 Correct 876 ms 157276 KB Output is correct
55 Correct 943 ms 156848 KB Output is correct
56 Correct 162 ms 51408 KB Output is correct
57 Correct 321 ms 51408 KB Output is correct
58 Correct 430 ms 52216 KB Output is correct
59 Correct 1375 ms 157236 KB Output is correct
60 Correct 3396 ms 193496 KB Output is correct
61 Correct 1281 ms 188256 KB Output is correct
62 Correct 1088 ms 157008 KB Output is correct
63 Correct 2692 ms 185500 KB Output is correct
64 Correct 1639 ms 183812 KB Output is correct
65 Correct 1276 ms 157520 KB Output is correct
66 Correct 1293 ms 157268 KB Output is correct
67 Correct 1654 ms 192556 KB Output is correct
68 Correct 1209 ms 192312 KB Output is correct
69 Correct 2647 ms 205360 KB Output is correct