oj.uz

답안 #904957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
904957 2024-01-12T11:53:16 Z Trisanu_Das 자리 배치 (IOI18_seats) C++17
37 / 100
 4000 ms 180840 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000005;
vector<int> r;
pair<int, int> V[MAX_N];
pair<int, int> mx[MAX_N], mi[MAX_N];
vector<int> lst;

struct inout_pq {
    priority_queue<int> in, out;

    void add(int x) { in.push(-x); }

    void delect(int x) { out.push(-x); }

    int return_top() {
        while (in.size() && out.size() && in.top() == out.top()) {
            in.pop();
            out.pop();
        }
        if (in.size()) return -in.top();
        return 0;
    }
} X[MAX_N], Y[MAX_N];

int h, w, ans;

int sp(int a, int b) {
    pair<int, int> x, y;
    swap(V[a], V[b]);
    if (a > b) swap(a, b);
    a = a ? a : a + 1;
    mx[0] = mi[0] = V[0];
    for (int i = a; i <= b; i++) {
        ans -= ((mx[i].first - mi[i].first + 1) * (mx[i].second - mi[i].second + 1) == (i + 1)) ? 1 : 0;
        mx[i].first = max(mx[i - 1].first, V[i].first);
        mx[i].second = max(mx[i - 1].second, V[i].second);
        mi[i].first = min(mi[i - 1].first, V[i].first);
        mi[i].second = min(mi[i - 1].second, V[i].second);
        ans += ((mx[i].first - mi[i].first + 1) * (mx[i].second - mi[i].second + 1) == (i + 1)) ? 1 : 0;
    }
    return ans;
}

void sp_init() {
    mx[0] = mi[0] = V[0];
    swap(V[0], V[h * w - 1]);
    ans = 1;
    ans = sp(0, h * w - 1);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    int i;
    h = H;
    w = W;
    for (i = 0; i < H * W; i++) V[i] = {R[i], C[i]};
    if (h + w >= 10000) {
        sp_init();
        return;
    }
    for (i = 0; i < H * W; i++) {
        X[R[i]].add(i);
        Y[C[i]].add(i);
    }
}

int swap_seats(int a, int b) {
    int i;
    if (h + w >= 10000) return sp(a, b);
    X[V[a].first].delect(a);
    Y[V[a].second].delect(a);
    X[V[b].first].delect(b);
    Y[V[b].second].delect(b);
    swap(V[a], V[b]);
    X[V[a].first].add(a);
    Y[V[a].second].add(a);
    X[V[b].first].add(b);
    Y[V[b].second].add(b);
    lst.clear();
    lst.resize(0);
    for (i = 0; i < h; i++) lst.push_back(X[i].return_top());
    for (i = 0; i < w; i++) lst.push_back(Y[i].return_top());
    sort(lst.begin(), lst.end());
    lst.erase(unique(lst.begin(), lst.end()), lst.end());
    pair<int, int> x, y;
    ans = 1;
    x = {V[0].first, V[0].first};
    y = {V[0].second, V[0].second};
    for (int p : lst) {
        ans += ((x.second - x.first + 1) * (y.second - y.first + 1) == p);
        y.first = min(y.first, V[p].second);
        y.second = max(y.second, V[p].second);
        x.first = min(x.first, V[p].first);
        x.second = max(x.second, V[p].first);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 127836 KB Output is correct
2 Correct 41 ms 128092 KB Output is correct
3 Correct 42 ms 128336 KB Output is correct
4 Correct 49 ms 128012 KB Output is correct
5 Correct 49 ms 128092 KB Output is correct
6 Correct 44 ms 128092 KB Output is correct
7 Correct 43 ms 128028 KB Output is correct
8 Correct 39 ms 128080 KB Output is correct
9 Correct 40 ms 128116 KB Output is correct
10 Correct 48 ms 127824 KB Output is correct
11 Correct 48 ms 127828 KB Output is correct
12 Correct 49 ms 128236 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 127836 KB Output is correct
2 Correct 41 ms 128092 KB Output is correct
3 Correct 42 ms 128336 KB Output is correct
4 Correct 49 ms 128012 KB Output is correct
5 Correct 49 ms 128092 KB Output is correct
6 Correct 44 ms 128092 KB Output is correct
7 Correct 43 ms 128028 KB Output is correct
8 Correct 39 ms 128080 KB Output is correct
9 Correct 40 ms 128116 KB Output is correct
10 Correct 48 ms 127824 KB Output is correct
11 Correct 48 ms 127828 KB Output is correct
12 Correct 49 ms 128236 KB Output is correct
13 Correct 57 ms 128340 KB Output is correct
14 Correct 61 ms 128164 KB Output is correct
15 Correct 115 ms 130056 KB Output is correct
16 Correct 118 ms 130060 KB Output is correct
17 Correct 1172 ms 128604 KB Output is correct
18 Correct 186 ms 128340 KB Output is correct
19 Correct 269 ms 128088 KB Output is correct
20 Correct 452 ms 128504 KB Output is correct
21 Correct 115 ms 129872 KB Output is correct
22 Correct 113 ms 130056 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 664 ms 159204 KB Output is correct
2 Correct 530 ms 158944 KB Output is correct
3 Correct 873 ms 158568 KB Output is correct
4 Correct 490 ms 158436 KB Output is correct
5 Correct 494 ms 158800 KB Output is correct
6 Correct 388 ms 158552 KB Output is correct
7 Correct 857 ms 158688 KB Output is correct
8 Correct 1033 ms 158548 KB Output is correct
9 Correct 604 ms 158448 KB Output is correct
10 Correct 362 ms 158428 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 128092 KB Output is correct
2 Correct 135 ms 130588 KB Output is correct
3 Correct 369 ms 158436 KB Output is correct
4 Correct 657 ms 159208 KB Output is correct
5 Correct 309 ms 164688 KB Output is correct
6 Correct 344 ms 180728 KB Output is correct
7 Correct 356 ms 180704 KB Output is correct
8 Correct 328 ms 180736 KB Output is correct
9 Correct 387 ms 180840 KB Output is correct
10 Correct 334 ms 180828 KB Output is correct
11 Correct 317 ms 180708 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 129236 KB Output is correct
2 Correct 64 ms 129544 KB Output is correct
3 Correct 119 ms 129808 KB Output is correct
4 Correct 823 ms 129788 KB Output is correct
5 Correct 766 ms 131072 KB Output is correct
6 Execution timed out 4043 ms 165092 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 127836 KB Output is correct
2 Correct 41 ms 128092 KB Output is correct
3 Correct 42 ms 128336 KB Output is correct
4 Correct 49 ms 128012 KB Output is correct
5 Correct 49 ms 128092 KB Output is correct
6 Correct 44 ms 128092 KB Output is correct
7 Correct 43 ms 128028 KB Output is correct
8 Correct 39 ms 128080 KB Output is correct
9 Correct 40 ms 128116 KB Output is correct
10 Correct 48 ms 127824 KB Output is correct
11 Correct 48 ms 127828 KB Output is correct
12 Correct 49 ms 128236 KB Output is correct
13 Correct 57 ms 128340 KB Output is correct
14 Correct 61 ms 128164 KB Output is correct
15 Correct 115 ms 130056 KB Output is correct
16 Correct 118 ms 130060 KB Output is correct
17 Correct 1172 ms 128604 KB Output is correct
18 Correct 186 ms 128340 KB Output is correct
19 Correct 269 ms 128088 KB Output is correct
20 Correct 452 ms 128504 KB Output is correct
21 Correct 115 ms 129872 KB Output is correct
22 Correct 113 ms 130056 KB Output is correct
23 Correct 664 ms 159204 KB Output is correct
24 Correct 530 ms 158944 KB Output is correct
25 Correct 873 ms 158568 KB Output is correct
26 Correct 490 ms 158436 KB Output is correct
27 Correct 494 ms 158800 KB Output is correct
28 Correct 388 ms 158552 KB Output is correct
29 Correct 857 ms 158688 KB Output is correct
30 Correct 1033 ms 158548 KB Output is correct
31 Correct 604 ms 158448 KB Output is correct
32 Correct 362 ms 158428 KB Output is correct
33 Correct 72 ms 128092 KB Output is correct
34 Correct 135 ms 130588 KB Output is correct
35 Correct 369 ms 158436 KB Output is correct
36 Correct 657 ms 159208 KB Output is correct
37 Correct 309 ms 164688 KB Output is correct
38 Correct 344 ms 180728 KB Output is correct
39 Correct 356 ms 180704 KB Output is correct
40 Correct 328 ms 180736 KB Output is correct
41 Correct 387 ms 180840 KB Output is correct
42 Correct 334 ms 180828 KB Output is correct
43 Correct 317 ms 180708 KB Output is correct
44 Correct 58 ms 129236 KB Output is correct
45 Correct 64 ms 129544 KB Output is correct
46 Correct 119 ms 129808 KB Output is correct
47 Correct 823 ms 129788 KB Output is correct
48 Correct 766 ms 131072 KB Output is correct
49 Execution timed out 4043 ms 165092 KB Time limit exceeded
50 Halted 0 ms 0 KB -