QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#932069#2743. SeatsKiharaTouma0 115ms38164kbC++143.4kb2025-03-12 07:47:242025-03-12 07:47:31

Judging History

This is the latest submission verdict.

  • [2025-03-12 07:47:31]
  • Judged
  • Verdict: 0
  • Time: 115ms
  • Memory: 38164kb
Show
  • [2025-03-12 07:47:24]
  • Submitted

answer

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

const int N = 1e6 + 10;
const int dx[5] = {0, 0, -1, 1, 0}, dy[5] = {0, -1, 0, 0, 1};
int n, m, mx;
vector<int> a[N];
pair<int, int> pos[N];

int t[N*4], tag[N*4], cnt[N*4];
void psd(int p){
    t[p<<1] += tag[p];
    t[p<<1|1] += tag[p];
    tag[p<<1] += tag[p];
    tag[p<<1|1] += tag[p];
    tag[p] = 0;
}
void upd(int p){
    if(t[p<<1] < t[p<<1|1]){
        t[p] = t[p<<1];
        cnt[p] = cnt[p<<1];
    } else if(t[p<<1] > t[p<<1|1]){
        t[p] = t[p<<1|1];
        cnt[p] = cnt[p<<1|1];
    } else {
        t[p] = t[p<<1];
        cnt[p] = cnt[p<<1] + cnt[p<<1|1];
    }
}
void build(int p, int l, int r){
    // printf("%d %d %d\n", p, l, r);
    if(l == r){
        t[p] = 1e9;
        cnt[p] = 1;
    } else {
        int mid = l + r >> 1;
        build(p<<1, l, mid);
        build(p<<1|1, mid+1, r);
        upd(p);
    }
}
void add(int p, int l, int r, int ql, int qr, int v){
    // if(p == 1) printf("%d %d %d\n", ql, qr, v);
    if(qr < l || r < ql){
        return;
    } else if(ql <= l && r <= qr){
        t[p] += v;
        tag[p] += v;
    } else {
        int mid = l + r >> 1;
        psd(p);
        add(p<<1, l, mid, ql, qr, v);
        add(p<<1|1, mid+1, r, ql, qr, v);
        upd(p);
    }
}

void upd(int x, int y, int op){
    add(1, 1, mx, a[x][y], min(a[x-1][y], a[x][y-1])-1, op);
    add(1, 1, mx, a[x][y], min(a[x+1][y], a[x][y-1])-1, op);
    add(1, 1, mx, a[x][y], min(a[x-1][y], a[x][y+1])-1, op);
    add(1, 1, mx, a[x][y], min(a[x+1][y], a[x][y+1])-1, op);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    n = H;
    m = W;
    mx = n * m;
    build(1, 1, mx);
    for(int i = 0; i <= m + 1; ++ i){
        a[0].push_back(mx + 1);
        a[n+1].push_back(mx + 1);
    }
    for(int i = 1; i <= n; ++ i){
        a[i].resize(m + 2);
        a[i][0] = a[i][m+1] = mx + 1;
    }
    for(int i = 0; i < mx; ++ i){
        a[R[i]+1][C[i]+1] = i + 1;
        pos[i+1] = make_pair(R[i] + 1, C[i] + 1);
    }
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            upd(i, j, 1);
        }
    }
}

int swap_seats(int aa, int bb){
    ++ aa;
    ++ bb;
    int xa = pos[aa].first, ya = pos[aa].second;
    int xb = pos[bb].first, yb = pos[bb].second;
    for(int i = 0; i < 5; ++ i){
        int xx = xa + dx[i], yy = ya + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            upd(xx, yy, -1);
        }
        xx = xb + dx[i], yy = yb + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            upd(xx, yy, -1);
        }
    }
    swap(a[xa][ya], a[xb][yb]);
    swap(pos[aa], pos[bb]);
    for(int i = 0; i < 5; ++ i){
        int xx = xa + dx[i], yy = ya + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            upd(xx, yy, 1);
        }
        xx = xb + dx[i], yy = yb + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            upd(xx, yy, 1);
        }
    }
    return cnt[1];
}

#ifndef ONLINE_JUDGE
int main(){
    // give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
    // printf("%d\n", swap_seats(0, 5));
    // printf("%d\n", swap_seats(0, 5));
    give_initial_chart(1, 5, {0, 0, 0, 0, 0}, {0, 1, 2, 3, 4});
    printf("%d\n", swap_seats(0, 1));
    printf("%d\n", swap_seats(0, 3));
    printf("%d\n", swap_seats(4, 0));
    return 0;
}
#endif
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 10ms
memory: 33184kb

input:

3 3 5000
2 2
1 2
0 2
0 1
0 0
2 1
1 1
1 0
2 0
6 0
5 7
6 4
3 2
0 2
0 2
7 0
7 0
3 2
3 6
0 2
3 5
2 6
2 0
8 6
0 6
1 3
1 8
8 1
4 2
1 8
2 5
1 3
7 0
6 5
6 3
2 8
8 2
1 3
8 5
6 3
8 0
4 8
6 8
7 8
4 3
3 6
5 0
8 5
1 7
2 6
1 2
5 4
5 1
7 6
8 4
7 3
6 8
8 3
0 3
6 3
0 8
0 5
7 2
0 3
7 5
4 5
3 5
1 0
0 8
7 0
2 5
5 8
7 4...

output:

3
3
3
3
2
3
2
3
3
3
3
3
3
2
1
1
1
3
1
1
3
3
3
1
1
1
1
1
1
4
4
1
2
2
3
3
3
3
2
3
4
4
4
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
2
1
2
1
1
1
1
1
2
2
2
2
2
2
2
2
2
3
3
3
2
2
2
2
2
2
2
1
3
4
3
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
1
1
3
1
2
2
2
2
2
1
1
1
4
4
4
1
1
2
2
2
1
1
1
1
1
1
3
1
...

result:

wrong answer 1st numbers differ - expected: '4', found: '3'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Wrong Answer

Test #33:

score: 6
Accepted
time: 48ms
memory: 34856kb

input:

101 101 5000
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 ...

output:

90
27
27
27
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
...

result:

ok 5000 numbers

Test #34:

score: 0
Wrong Answer
time: 115ms
memory: 38164kb

input:

300 300 5000
0 0
0 1
1 1
1 0
0 2
1 2
2 2
2 1
2 0
0 3
1 3
2 3
3 3
3 2
3 1
3 0
0 4
1 4
2 4
3 4
4 4
4 3
4 2
4 1
4 0
0 5
1 5
2 5
3 5
4 5
5 5
5 4
5 3
5 2
5 1
5 0
0 6
1 6
2 6
3 6
4 6
5 6
6 6
6 5
6 4
6 3
6 2
6 1
6 0
0 7
1 7
2 7
3 7
4 7
5 7
6 7
7 7
7 6
7 5
7 4
7 3
7 2
33 46
7 0
0 8
1 8
2 8
3 8
4 8
5 8
6 8
7...

output:

18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
18
...

result:

wrong answer 4952nd numbers differ - expected: '145', found: '147'

Subtask #5:

score: 0
Wrong Answer

Test #44:

score: 33
Accepted
time: 29ms
memory: 31664kb

input:

1 3 50000
0 1
0 2
0 0
0 2
2 0
2 1
0 1
1 0
0 1
1 2
1 2
1 2
0 2
1 0
0 2
2 0
1 2
2 1
2 0
0 1
0 2
1 2
1 0
1 0
1 2
0 1
1 0
0 2
0 2
2 1
0 2
1 0
1 2
2 1
2 1
1 2
0 1
1 2
0 1
0 2
1 2
0 2
2 1
2 0
1 2
1 0
1 0
2 1
1 0
1 0
2 1
1 2
0 2
2 0
1 0
2 0
0 2
1 0
0 2
1 2
2 1
0 1
0 2
1 0
2 1
2 0
1 2
0 1
2 0
2 1
2 0
0 2
1 ...

output:

2
3
3
3
3
3
2
3
2
3
3
3
3
2
3
3
3
2
3
3
3
2
2
2
3
2
3
3
3
3
3
3
3
3
2
2
3
3
2
3
3
2
2
2
3
3
3
2
3
3
3
3
2
3
3
3
2
3
3
2
2
3
3
2
2
3
3
2
3
3
2
2
2
2
3
2
3
3
3
3
3
2
3
2
3
2
2
2
2
3
3
3
3
3
3
3
2
2
3
3
3
2
3
2
3
3
3
2
2
3
2
3
3
3
3
3
3
3
3
3
2
3
3
2
3
3
3
3
2
3
3
3
3
3
3
2
3
3
3
3
3
2
3
3
2
3
3
3
3
2
...

result:

ok 50000 numbers

Test #45:

score: 0
Wrong Answer
time: 75ms
memory: 31944kb

input:

1 10 50000
0 7
0 5
0 8
0 6
0 0
0 1
0 2
0 4
0 3
0 9
6 0
5 8
9 7
8 3
1 3
2 5
9 8
8 3
3 0
6 0
3 5
2 0
2 8
2 5
8 3
8 5
7 2
2 8
0 3
3 2
2 0
3 5
2 0
5 8
5 0
9 2
2 8
2 1
5 3
8 9
1 0
5 6
4 7
5 7
0 9
1 3
3 0
9 3
8 9
3 6
4 0
2 7
9 2
8 2
2 6
5 7
7 4
2 5
3 4
0 1
9 1
9 7
0 1
6 4
9 5
6 8
0 2
9 5
3 1
1 8
9 2
6 8
1...

output:

3
3
2
2
3
4
4
2
2
2
2
2
2
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
4
3
2
2
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
2
2
2
5
6
5
2
3
2
2
2
2
2
4
4
4
2
2
2
2
2
2
3
3
3
3
3
3
3
5
3
3
3
3
3
2
2
2
2
3
3
3
4
4
3
8
7
3
2
2
2
2
2
3
2
2
2
2
3
3
2
2
3
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
...

result:

wrong answer 8th numbers differ - expected: '6', found: '2'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2025-04-15 11:16:06 | OpenSource Project