제출 #131975

#제출 시각아이디문제언어결과실행 시간메모리
131975Just_Solve_The_Problem자리 배치 (IOI18_seats)C++11
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> #include "seats.h" #include "grader.cpp" using namespace std; const int N = (int)1e6 + 7; vector <int> vec; int n; struct T { pair <int, int> tree[N * 4]; int add[N * 4]; T() { } void push(int v, int l, int r) { if (add[v] == 0) return ; if (l != r) { add[v + v] += add[v]; add[v + v + 1] += add[v]; } tree[v].first += add[v]; add[v] = 0; } pair <int, int> gather(pair <int, int> l, pair <int, int> r) { pair <int, int> res; if (l.first == r.first) { res = l; res.second += r.second; } else if (l.first < r.first) { res = l; } else { res = r; } return res; } void build(int v = 1, int l = 0, int r = n - 1) { if (l == r) { tree[v] = {0, 1}; add[v] = 0; return ; } int mid = (l + r) >> 1; build(v + v, l, mid); build(v + v + 1, mid + 1, r); tree[v] = gather(tree[v + v], tree[v + v + 1]); } void upd(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1) { push(v, tl, tr); if (tl > r || tr < l) return ; if (l <= tl && tr <= r) { add[v] += val; push(v, tl, tr); return ; } int mid = (tl + tr) >> 1; upd(l, r, val, v + v, tl, mid); upd(l, r, val, v + v + 1, mid + 1, tr); tree[v] = gather(tree[v + v], tree[v + v + 1]); //cout << v << ' ' << tl << ' ' << tr << ' ' << tree[v].first << ' ' << tree[v].second << endl; } pair <int, int> get(int l, int r, int v = 1, int tl = 0, int tr = n - 1) { push(v, tl, tr); if (tl > r || tr < l) return {1e9, 0}; if (l <= tl && tr <= r) return tree[v]; int mid = (tl + tr) >> 1; return gather(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr)); } }; T tr; vector <int> r, c; int getval(int x) { int val = 0; val += (c[x] == 0 || vec[c[x] - 1] > x); val += (c[x] == n - 1 || vec[c[x] + 1] > x); return val; } void add(int x) { int val = getval(x); if (val == 2) { tr.upd(x, n - 1, 2); } else if (val == 0) { tr.upd(x, n - 1, -2); } } void del(int x) { int val = getval(x); if (val == 2) { tr.upd(x, n - 1, -2); } else if (val == 0) { tr.upd(x, n - 1, 2); } } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { r = R; c = C; n = H * W; tr.build(); vec.resize(n); for (int i = 0; i < n; i++) { vec[C[i]] = i; } for (int i = 0; i < n; i++) { add(i); } //for (int to : vec) { //cout << to << ' '; //} //cout << endl; //for (int i = 0; i < n; i++) { //cout << tr.get(i, i).first << ' '; //} //cout << endl; //cout << tr.get(0, n - 1).second << endl; } int used[N]; void rollback(int x) { if (!used[x]) { del(x); used[x] = 1; } if (c[x] > 0 && !used[vec[c[x] - 1]]) { used[vec[c[x] - 1]] = 1; del(vec[c[x] - 1]); } if (c[x] + 1 < n && !used[vec[c[x] + 1]]) { used[vec[c[x] + 1]] = 1; del(vec[c[x] + 1]); } } void add1(int x) { if (used[x] == 1) { add(x); used[x] = 0; } if (c[x] > 0 && used[vec[c[x] - 1]]) { add(vec[c[x] - 1]); used[vec[c[x] - 1]] = 0; } if (c[x] + 1 < n && used[vec[c[x] + 1]]) { add(vec[c[x] + 1]); used[vec[c[x] + 1]] = 0; } } int swap_seats(int a, int b) { rollback(a); rollback(b); swap(c[a], c[b]); vec[c[a]] = a; vec[c[b]] = b; add1(a); add1(b); //for (int i = 0; i < n; i++) { //cout << tr.get(i, i).first << ' '; //} //cout << endl; return tr.get(0, n - 1).second; }

컴파일 시 표준 에러 (stderr) 메시지

/tmp/cciEdzmF.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUHSaan.o:seats.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status