oj.uz

Submission #81209

# Submission time Handle Problem Language Result Execution time Memory
81209 2018-10-24T05:48:47 Z cki86201 Seats (IOI18_seats) C++11
100 / 100
 3874 ms 77716 KB 
#include "seats.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int T[1<<21], A[1<<21], cnt[1<<21];
int R[1000010], C[1000010];
int N, M, P;

void init(int rt, int l, int r) {
    cnt[rt] = r - l + 1;
    if(l == r) return;
    int m = (l + r) >> 1;
    init(rt<<1, l, m);
    init(rt<<1|1, m+1, r);
}

inline void pushup(int rt) {
    if(T[rt<<1] == T[rt<<1|1]) cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1], T[rt] = T[rt<<1];
    else if(T[rt<<1] < T[rt<<1|1]) cnt[rt] = cnt[rt<<1], T[rt] = T[rt<<1];
    else cnt[rt] = cnt[rt<<1|1], T[rt] = T[rt<<1|1];
}

void add(int rt, int l, int r, int s, int e, int c) {
    if(s <= l && r <= e) {
        T[rt] += c;
        A[rt] += c;
        return;
    }
    if(A[rt]) {
        T[rt<<1] += A[rt];
        A[rt<<1] += A[rt];
        T[rt<<1|1] += A[rt];
        A[rt<<1|1] += A[rt];
        A[rt] = 0;
    }
    int m = (l + r) >> 1;
    if(s <= m) add(rt<<1, l, m, s, e, c);
    if(m < e) add(rt<<1|1, m+1, r, s, e, c);
    pushup(rt);
}

void add(int l, int r, int v) {
    add(1, 1, P, l, r, v);
}

int rval[1000010];

void get_val(int x, int y, int rr[]) {
    int rz = 0;
    for(int dx : {0,1}) for(int dy : {0,1}) {
        int ni = x + dx, nj = y + dy, val = P + 1;
        if(1 <= ni && ni <= N && 1 <= nj && nj <= M) {
            val = rval[(ni-1)*M+(nj-1)];
        }
        rr[rz++] = val;
    }
    sort(rr, rr+4);
}

void give_initial_chart(int H, int W, std::vector<int> tR, std::vector<int> tC) {
    N = H; M = W;
    P = N * M;
    init(1, 1, P);
    rep(i, P) R[i + 1] = tR[i] + 1, C[i + 1] = tC[i] + 1;
    for(int i=1;i<=P;i++) rval[(R[i]-1)*M+(C[i]-1)] = i;
    rep(i, N+1) rep(j, M+1) {
        int tt[4];
        get_val(i, j, tt);
        if(tt[0]<tt[1]) add(tt[0], tt[1]-1, 1);
        if(tt[2]<tt[3]) add(tt[2], tt[3]-1, 100);
    }
}

void change(int r, int c, int x) {
    for(int dx:{-1,0}) for(int dy:{-1,0}) {
        int tt[4];
        get_val(r+dx, c+dy, tt);
        if(tt[0]<tt[1]) add(tt[0], tt[1]-1, -1);
        if(tt[2]<tt[3]) add(tt[2], tt[3]-1, -100);
    }
    rval[(r-1)*M+(c-1)] = x;
    for(int dx:{-1,0}) for(int dy:{-1,0}) {
        int tt[4];
        get_val(r+dx, c+dy, tt);
        if(tt[0]<tt[1]) add(tt[0], tt[1]-1, 1);
        if(tt[2]<tt[3]) add(tt[2], tt[3]-1, 100);
    }
}

int swap_seats(int a, int b) {
    ++a; ++b;
    change(R[a], C[a], b);
    change(R[b], C[b], a);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    return cnt[1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 22 ms 700 KB Output is correct
3 Correct 35 ms 700 KB Output is correct
4 Correct 24 ms 700 KB Output is correct
5 Correct 19 ms 700 KB Output is correct
6 Correct 32 ms 824 KB Output is correct
7 Correct 33 ms 824 KB Output is correct
8 Correct 31 ms 824 KB Output is correct
9 Correct 29 ms 892 KB Output is correct
10 Correct 32 ms 1012 KB Output is correct
11 Correct 30 ms 1012 KB Output is correct
12 Correct 19 ms 1080 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 22 ms 700 KB Output is correct
3 Correct 35 ms 700 KB Output is correct
4 Correct 24 ms 700 KB Output is correct
5 Correct 19 ms 700 KB Output is correct
6 Correct 32 ms 824 KB Output is correct
7 Correct 33 ms 824 KB Output is correct
8 Correct 31 ms 824 KB Output is correct
9 Correct 29 ms 892 KB Output is correct
10 Correct 32 ms 1012 KB Output is correct
11 Correct 30 ms 1012 KB Output is correct
12 Correct 19 ms 1080 KB Output is correct
13 Correct 76 ms 1780 KB Output is correct
14 Correct 91 ms 1808 KB Output is correct
15 Correct 51 ms 1808 KB Output is correct
16 Correct 34 ms 1808 KB Output is correct
17 Correct 62 ms 1984 KB Output is correct
18 Correct 57 ms 1984 KB Output is correct
19 Correct 56 ms 2044 KB Output is correct
20 Correct 44 ms 2300 KB Output is correct
21 Correct 39 ms 2368 KB Output is correct
22 Correct 36 ms 2552 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2451 ms 53824 KB Output is correct
2 Correct 1196 ms 54116 KB Output is correct
3 Correct 1132 ms 54116 KB Output is correct
4 Correct 874 ms 54116 KB Output is correct
5 Correct 1002 ms 54116 KB Output is correct
6 Correct 880 ms 54116 KB Output is correct
7 Correct 1016 ms 54264 KB Output is correct
8 Correct 1101 ms 54264 KB Output is correct
9 Correct 1201 ms 54328 KB Output is correct
10 Correct 1101 ms 54456 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 54456 KB Output is correct
2 Correct 186 ms 54456 KB Output is correct
3 Correct 964 ms 54472 KB Output is correct
4 Correct 2503 ms 54472 KB Output is correct
5 Correct 856 ms 54472 KB Output is correct
6 Correct 2143 ms 54472 KB Output is correct
7 Correct 903 ms 54472 KB Output is correct
8 Correct 1242 ms 54796 KB Output is correct
9 Correct 1106 ms 54796 KB Output is correct
10 Correct 1002 ms 54796 KB Output is correct
11 Correct 922 ms 54796 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 54796 KB Output is correct
2 Correct 117 ms 54796 KB Output is correct
3 Correct 178 ms 54796 KB Output is correct
4 Correct 225 ms 54796 KB Output is correct
5 Correct 385 ms 54796 KB Output is correct
6 Correct 1391 ms 55184 KB Output is correct
7 Correct 1779 ms 55184 KB Output is correct
8 Correct 1335 ms 55312 KB Output is correct
9 Correct 3271 ms 55312 KB Output is correct
10 Correct 1266 ms 55312 KB Output is correct
11 Correct 1316 ms 55312 KB Output is correct
12 Correct 1265 ms 55312 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 22 ms 700 KB Output is correct
3 Correct 35 ms 700 KB Output is correct
4 Correct 24 ms 700 KB Output is correct
5 Correct 19 ms 700 KB Output is correct
6 Correct 32 ms 824 KB Output is correct
7 Correct 33 ms 824 KB Output is correct
8 Correct 31 ms 824 KB Output is correct
9 Correct 29 ms 892 KB Output is correct
10 Correct 32 ms 1012 KB Output is correct
11 Correct 30 ms 1012 KB Output is correct
12 Correct 19 ms 1080 KB Output is correct
13 Correct 76 ms 1780 KB Output is correct
14 Correct 91 ms 1808 KB Output is correct
15 Correct 51 ms 1808 KB Output is correct
16 Correct 34 ms 1808 KB Output is correct
17 Correct 62 ms 1984 KB Output is correct
18 Correct 57 ms 1984 KB Output is correct
19 Correct 56 ms 2044 KB Output is correct
20 Correct 44 ms 2300 KB Output is correct
21 Correct 39 ms 2368 KB Output is correct
22 Correct 36 ms 2552 KB Output is correct
23 Correct 2451 ms 53824 KB Output is correct
24 Correct 1196 ms 54116 KB Output is correct
25 Correct 1132 ms 54116 KB Output is correct
26 Correct 874 ms 54116 KB Output is correct
27 Correct 1002 ms 54116 KB Output is correct
28 Correct 880 ms 54116 KB Output is correct
29 Correct 1016 ms 54264 KB Output is correct
30 Correct 1101 ms 54264 KB Output is correct
31 Correct 1201 ms 54328 KB Output is correct
32 Correct 1101 ms 54456 KB Output is correct
33 Correct 69 ms 54456 KB Output is correct
34 Correct 186 ms 54456 KB Output is correct
35 Correct 964 ms 54472 KB Output is correct
36 Correct 2503 ms 54472 KB Output is correct
37 Correct 856 ms 54472 KB Output is correct
38 Correct 2143 ms 54472 KB Output is correct
39 Correct 903 ms 54472 KB Output is correct
40 Correct 1242 ms 54796 KB Output is correct
41 Correct 1106 ms 54796 KB Output is correct
42 Correct 1002 ms 54796 KB Output is correct
43 Correct 922 ms 54796 KB Output is correct
44 Correct 62 ms 54796 KB Output is correct
45 Correct 117 ms 54796 KB Output is correct
46 Correct 178 ms 54796 KB Output is correct
47 Correct 225 ms 54796 KB Output is correct
48 Correct 385 ms 54796 KB Output is correct
49 Correct 1391 ms 55184 KB Output is correct
50 Correct 1779 ms 55184 KB Output is correct
51 Correct 1335 ms 55312 KB Output is correct
52 Correct 3271 ms 55312 KB Output is correct
53 Correct 1266 ms 55312 KB Output is correct
54 Correct 1316 ms 55312 KB Output is correct
55 Correct 1265 ms 55312 KB Output is correct
56 Correct 142 ms 55312 KB Output is correct
57 Correct 321 ms 55312 KB Output is correct
58 Correct 546 ms 55312 KB Output is correct
59 Correct 1920 ms 73940 KB Output is correct
60 Correct 3806 ms 77572 KB Output is correct
61 Correct 1797 ms 77620 KB Output is correct
62 Correct 1439 ms 77716 KB Output is correct
63 Correct 3874 ms 77716 KB Output is correct
64 Correct 2133 ms 77716 KB Output is correct
65 Correct 1919 ms 77716 KB Output is correct
66 Correct 2131 ms 77716 KB Output is correct
67 Correct 2024 ms 77716 KB Output is correct
68 Correct 1463 ms 77716 KB Output is correct
69 Correct 3218 ms 77716 KB Output is correct