답안 #79836 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79836	2018-10-16T17:20:49 Z	Milki	자리 배치 (IOI18_seats)	C++14	100 / 100	2274 ms	135544 KB

seats

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((long long) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

const int off = 1 << 21;
const int MAXN = 1e6 + 5;
const int INF = 1e9;
int kraj;

struct Tournament{
    point t[2 * off];
    int p[2 * off];

    Tournament(){
        REP(i, 2 * off)
            t[i] = point(INF, 0);
    }
    void build(){
        for(int i = off - 1; i > 0; --i)
            t[i] = merge(t[i * 2], t[i * 2 + 1]);
    }
    void add(int x, int val){
        t[x + off] = point(val, 1);
    }
    void prop(int x){
        t[x].first += p[x];
        if(x < off){
            p[x * 2] += p[x];
            p[x * 2 + 1] += p[x];
        }
        p[x] = 0;
    }
    point merge(point a, point b){
        point ret = point(min(a.first, b.first), 0);
        if(a.first == ret.first) ret.second += a.second;
        if(b.first == ret.first) ret.second += b.second;
        return ret;
    }
    void update(int x, int lo, int hi, int a, int b, int val){
        if(a >= b) return;

        if(lo >= a && hi <= b){
            p[x] += val;
            prop(x);
            return;
        }
        prop(x);
        if(lo >= b || hi <= a) return;

        int mid = (lo + hi) >> 1;
        update(x * 2, lo, mid, a, b, val);
        update(x * 2 + 1, mid, hi, a, b, val);

        t[x] = merge(t[x * 2], t[x * 2 + 1]);
    }
    point get(int x, int lo, int hi, int a, int b){
        prop(x);
        if(lo >= a && hi <= b) return t[x];
        if(lo >= b || hi <= a) return point(-1, -1);

        int mid = (lo + hi) >> 1;
        point A = get(x * 2, lo, mid, a, b);
        point B = get(x * 2 + 1, mid, hi, a, b);

        return merge(A, B);
    }
} T;

const int dx[4][3] = { {0, -1, -1}, {-1, -1, 0}, {0, 1, 1}, {1, 1, 0} };
const int dy[4][3] = { {-1, -1, 0}, {0, 1, 1}, {1, 1, 0}, {0, -1, -1} };

vector <int> v[MAXN];

int prefix_update(int x, int y){
    int old_val = 0, val = 0;
    REP(i, 4){
        int cnt = 0;
        REP(j, 3){
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            if(v[nx][ny] < v[x][y]) cnt ++;
        }
        if(cnt == 1 || cnt == 3) old_val ++;
    }
    REP(i, 4){
        int cnt = 0;
        REP(j, 3){
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            if(v[nx][ny] < v[x][y]) cnt ++;
        }
        if(cnt == 0 || cnt == 2) val ++;
    }
    return val - old_val;
}

vector <int> row, col;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    REP(i, H + 2){
        v[i].reserve(W + 2);
    }

    REP(i, H + 2)
        v[i][0] = v[i][W + 1] = INF;
    REP(i, W + 2)
        v[0][i] = v[H + 1][i] = INF;

    REP(i, H + 2)
        REP(j, W + 2)
            v[i][j] = INF;
    row.reserve(H * W + 1); col.reserve(H * W + 1);

    int pref = 0;
    REP(i, H * W){
        R[i] ++; C[i] ++;
        row.pb(R[i]); col.pb(C[i]);
        v[R[i]][C[i]] = i;
        pref += prefix_update(R[i], C[i]);
        T.add(i, pref);
    }
    T.build();
    kraj = H * W;
}

void update(int x, int y, int val){
    REP(i, 4){
        vector <int> tmp;
        REP(j, 3){
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            tmp.pb(v[nx][ny]);
        }
        tmp.pb(v[x][y]);
        sort(tmp.begin(), tmp.end());
        REP(j, 4)
            if(tmp[j] == INF)
                tmp[j] = kraj;

        assert(v[x][y] != INF);
        if(tmp[0] == v[x][y]){
            T.update(1, 0, off, tmp[0], tmp[1], val);
            T.update(1, 0, off, tmp[1], tmp[2], -val);
            T.update(1, 0, off, tmp[2], tmp[3], val);
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        else if(tmp[1] == v[x][y]){
            T.update(1, 0, off, tmp[1], tmp[2], -val);
            T.update(1, 0, off, tmp[2], tmp[3], val);
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        else if(tmp[2] == v[x][y]){
            T.update(1, 0, off, tmp[2], tmp[3], val);
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        else if(tmp[3] == v[x][y]){
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        /*else if(tmp[1] == v[x][y] && tmp[2] != INF)
            T.update(1, 0, off, tmp[1], tmp[2], -val);
        else if(tmp[1] == v[x][y] && tmp[2] == INF)
            T.update(1, 0, off, tmp[1], kraj, -val);
        */
    }
}

int swap_seats(int a, int b){
    int x1, y1, x2, y2;
    x1 = row[a], y1 = col[a];
    x2 = row[b], y2 = col[b];

    update(x1, y1, -1);
    update(x2, y2, -1);
    swap(v[x1][y1], v[x2][y2]);
    swap(row[a], row[b]);
    swap(col[a], col[b]);
    update(x1, y1, 1);
    update(x2, y2, 1);

    return T.get(1, 0, off, 0, off).second;
}

/*int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
} */

Compilation message

seats.cpp:15:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
 int read_int() {
     ^~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	56952 KB	Output is correct
2	Correct	171 ms	57108 KB	Output is correct
3	Correct	180 ms	57108 KB	Output is correct
4	Correct	142 ms	57108 KB	Output is correct
5	Correct	140 ms	57108 KB	Output is correct
6	Correct	161 ms	57108 KB	Output is correct
7	Correct	186 ms	57148 KB	Output is correct
8	Correct	171 ms	57300 KB	Output is correct
9	Correct	189 ms	57300 KB	Output is correct
10	Correct	175 ms	57304 KB	Output is correct
11	Correct	164 ms	57304 KB	Output is correct
12	Correct	165 ms	57456 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	56952 KB	Output is correct
2	Correct	171 ms	57108 KB	Output is correct
3	Correct	180 ms	57108 KB	Output is correct
4	Correct	142 ms	57108 KB	Output is correct
5	Correct	140 ms	57108 KB	Output is correct
6	Correct	161 ms	57108 KB	Output is correct
7	Correct	186 ms	57148 KB	Output is correct
8	Correct	171 ms	57300 KB	Output is correct
9	Correct	189 ms	57300 KB	Output is correct
10	Correct	175 ms	57304 KB	Output is correct
11	Correct	164 ms	57304 KB	Output is correct
12	Correct	165 ms	57456 KB	Output is correct
13	Correct	186 ms	57880 KB	Output is correct
14	Correct	194 ms	57880 KB	Output is correct
15	Correct	144 ms	57980 KB	Output is correct
16	Correct	145 ms	58292 KB	Output is correct
17	Correct	168 ms	58292 KB	Output is correct
18	Correct	177 ms	58292 KB	Output is correct
19	Correct	173 ms	58292 KB	Output is correct
20	Correct	161 ms	58436 KB	Output is correct
21	Correct	143 ms	58456 KB	Output is correct
22	Correct	144 ms	58880 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	771 ms	98340 KB	Output is correct
2	Correct	589 ms	98468 KB	Output is correct
3	Correct	629 ms	103840 KB	Output is correct
4	Correct	633 ms	103840 KB	Output is correct
5	Correct	645 ms	103840 KB	Output is correct
6	Correct	562 ms	103840 KB	Output is correct
7	Correct	584 ms	103840 KB	Output is correct
8	Correct	716 ms	103840 KB	Output is correct
9	Correct	583 ms	103840 KB	Output is correct
10	Correct	575 ms	103840 KB	Output is correct

Subtask #4
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	225 ms	103840 KB	Output is correct
2	Correct	221 ms	103840 KB	Output is correct
3	Correct	563 ms	108052 KB	Output is correct
4	Correct	692 ms	108056 KB	Output is correct
5	Correct	514 ms	115976 KB	Output is correct
6	Correct	996 ms	135532 KB	Output is correct
7	Correct	557 ms	135532 KB	Output is correct
8	Correct	603 ms	135532 KB	Output is correct
9	Correct	610 ms	135532 KB	Output is correct
10	Correct	578 ms	135532 KB	Output is correct
11	Correct	576 ms	135532 KB	Output is correct

Subtask #5
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	852 ms	135532 KB	Output is correct
2	Correct	907 ms	135532 KB	Output is correct
3	Correct	938 ms	135532 KB	Output is correct
4	Correct	828 ms	135532 KB	Output is correct
5	Correct	912 ms	135532 KB	Output is correct
6	Correct	1327 ms	135532 KB	Output is correct
7	Correct	1407 ms	135532 KB	Output is correct
8	Correct	1369 ms	135532 KB	Output is correct
9	Correct	1547 ms	135532 KB	Output is correct
10	Correct	1399 ms	135532 KB	Output is correct
11	Correct	1290 ms	135532 KB	Output is correct
12	Correct	1269 ms	135532 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	56952 KB	Output is correct
2	Correct	171 ms	57108 KB	Output is correct
3	Correct	180 ms	57108 KB	Output is correct
4	Correct	142 ms	57108 KB	Output is correct
5	Correct	140 ms	57108 KB	Output is correct
6	Correct	161 ms	57108 KB	Output is correct
7	Correct	186 ms	57148 KB	Output is correct
8	Correct	171 ms	57300 KB	Output is correct
9	Correct	189 ms	57300 KB	Output is correct
10	Correct	175 ms	57304 KB	Output is correct
11	Correct	164 ms	57304 KB	Output is correct
12	Correct	165 ms	57456 KB	Output is correct
13	Correct	186 ms	57880 KB	Output is correct
14	Correct	194 ms	57880 KB	Output is correct
15	Correct	144 ms	57980 KB	Output is correct
16	Correct	145 ms	58292 KB	Output is correct
17	Correct	168 ms	58292 KB	Output is correct
18	Correct	177 ms	58292 KB	Output is correct
19	Correct	173 ms	58292 KB	Output is correct
20	Correct	161 ms	58436 KB	Output is correct
21	Correct	143 ms	58456 KB	Output is correct
22	Correct	144 ms	58880 KB	Output is correct
23	Correct	771 ms	98340 KB	Output is correct
24	Correct	589 ms	98468 KB	Output is correct
25	Correct	629 ms	103840 KB	Output is correct
26	Correct	633 ms	103840 KB	Output is correct
27	Correct	645 ms	103840 KB	Output is correct
28	Correct	562 ms	103840 KB	Output is correct
29	Correct	584 ms	103840 KB	Output is correct
30	Correct	716 ms	103840 KB	Output is correct
31	Correct	583 ms	103840 KB	Output is correct
32	Correct	575 ms	103840 KB	Output is correct
33	Correct	225 ms	103840 KB	Output is correct
34	Correct	221 ms	103840 KB	Output is correct
35	Correct	563 ms	108052 KB	Output is correct
36	Correct	692 ms	108056 KB	Output is correct
37	Correct	514 ms	115976 KB	Output is correct
38	Correct	996 ms	135532 KB	Output is correct
39	Correct	557 ms	135532 KB	Output is correct
40	Correct	603 ms	135532 KB	Output is correct
41	Correct	610 ms	135532 KB	Output is correct
42	Correct	578 ms	135532 KB	Output is correct
43	Correct	576 ms	135532 KB	Output is correct
44	Correct	852 ms	135532 KB	Output is correct
45	Correct	907 ms	135532 KB	Output is correct
46	Correct	938 ms	135532 KB	Output is correct
47	Correct	828 ms	135532 KB	Output is correct
48	Correct	912 ms	135532 KB	Output is correct
49	Correct	1327 ms	135532 KB	Output is correct
50	Correct	1407 ms	135532 KB	Output is correct
51	Correct	1369 ms	135532 KB	Output is correct
52	Correct	1547 ms	135532 KB	Output is correct
53	Correct	1399 ms	135532 KB	Output is correct
54	Correct	1290 ms	135532 KB	Output is correct
55	Correct	1269 ms	135532 KB	Output is correct
56	Correct	1064 ms	135532 KB	Output is correct
57	Correct	1196 ms	135532 KB	Output is correct
58	Correct	1284 ms	135532 KB	Output is correct
59	Correct	1925 ms	135532 KB	Output is correct
60	Correct	2266 ms	135532 KB	Output is correct
61	Correct	1758 ms	135532 KB	Output is correct
62	Correct	1602 ms	135532 KB	Output is correct
63	Correct	2121 ms	135532 KB	Output is correct
64	Correct	1827 ms	135532 KB	Output is correct
65	Correct	1740 ms	135532 KB	Output is correct
66	Correct	1984 ms	135532 KB	Output is correct
67	Correct	1798 ms	135532 KB	Output is correct
68	Correct	1686 ms	135532 KB	Output is correct
69	Correct	2274 ms	135544 KB	Output is correct

답안 #79836

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 6.0 / 6.0

Subtask #3 20.0 / 20.0

Subtask #4 6.0 / 6.0

Subtask #5 33.0 / 33.0

Subtask #6 30.0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
6.0 / 6.0

Subtask #3
20.0 / 20.0

Subtask #4
6.0 / 6.0

Subtask #5
33.0 / 33.0

Subtask #6
30.0 / 30.0