제출 #1010973

#제출 시각아이디문제언어결과실행 시간메모리
1010973boris_mihov자리 배치 (IOI18_seats)C++17
33 / 100
2636 ms167392 KiB
#include "seats.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 1 << 20; const int INF = 1e9; int n, m; struct SegmentTreeLazy { struct Node { int min; int cnt; int lazy; Node() { min = cnt = lazy = 0; } friend Node operator + (const Node &left, const Node &right) { Node res; res.min = std::min(left.min, right.min); if (res.min == left.min) res.cnt += left.cnt; if (res.min == right.min) res.cnt += right.cnt; return res; } }; Node tree[2*MAXN]; void build(int l, int r, int node) { if (l == r) { tree[node].min = 0; tree[node].cnt = 1; return; } int mid = l + r >> 1; build(l, mid, 2*node); build(mid + 1, r, 2*node + 1); tree[node] = tree[2*node] + tree[2*node + 1]; } void push(int node, int l, int r) { if (tree[node].lazy == 0) { return; } tree[node].min += tree[node].lazy; if (l < r) { tree[2*node].lazy += tree[node].lazy; tree[2*node + 1].lazy += tree[node].lazy; } tree[node].lazy = 0; } void update(int l, int r, int node, int queryL, int queryR, int queryVal) { push(node, l, r); if (queryR < l || r < queryL) { return; } if (queryL <= l && r <= queryR) { tree[node].lazy = queryVal; push(node, l, r); return; } int mid = l + r >> 1; update(l, mid, 2*node, queryL, queryR, queryVal); update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal); tree[node] = tree[2*node] + tree[2*node + 1]; } Node query(int l, int r, int node, int queryL, int queryR) { push(node, l, r); if (queryL <= l && r <= queryR) { return tree[node]; } Node res; res.min = INF; int mid = l + r >> 1; if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR); if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR); return res; } void build() { build(1, n * m, 1); } void update(int l, int r, int val) { // std::cout << "singular update: " << l << ' ' << r << ' ' << val << '\n'; update(1, n * m, 1, l, r, val); } int query(int l, int r, int value) { Node res = query(1, n * m, 1, l, r); // std::cout << "reeeessss: " << res.min << ' ' << res.cnt << '\n'; if (res.min != value) return 0; return res.cnt; } }; struct SegmentTreeMinMax { struct Node { int min; int max; Node() { min = INF; max = 0; } friend Node operator + (const Node &left, const Node &right) { Node res; res.min = std::min(left.min, right.min); res.max = std::max(left.max, right.max); return res; } }; Node tree[2*MAXN]; void build(int l, int r, int node, std::vector <int> &v) { if (l == r) { // std::cout << "set: " << l << " = " << v[l] << '\n'; tree[node].min = tree[node].max = v[l]; return; } int mid = l + r >> 1; build(l, mid, 2*node, v); build(mid + 1, r, 2*node + 1, v); tree[node] = tree[2*node] + tree[2*node + 1]; } void update(int l, int r, int node, int queryPos, int queryVal) { if (l == r) { tree[node].min = tree[node].max = queryVal; return; } int mid = l + r >> 1; if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal); else update(mid + 1, r, 2*node + 1, queryPos, queryVal); tree[node] = tree[2*node] + tree[2*node + 1]; } int search(int l, int r, int node, int value) { if (l == r) { if (tree[node].min != value) return -1; return l; } int mid = l + r >> 1; if (tree[2*node].min == value && tree[2*node].max == value) { int res = search(mid + 1, r, 2*node + 1, value); if (res != -1) return res; return mid; } return search(l, mid, 2*node, value); } void build(std::vector <int> &v) { build(1, n * m, 1, v); } void update(int pos, int val) { update(1, n * m, 1, pos, val); } int search(int value) { return search(1, n * m, 1, value); } }; SegmentTreeLazy treeRect; SegmentTreeLazy treeLineRow; SegmentTreeLazy treeLineCol; SegmentTreeMinMax treeRow, treeCol; std::vector <int> t[MAXN]; std::vector <int> r, c; void addL(int row, int col) { // std::cout << "addL: " << row << ' ' << col << '\n' << std::flush; if (row > n || col > m || row == 1 || col == 1) { return; } std::vector <int> vals; vals.push_back(t[row][col]); vals.push_back(t[row - 1][col]); vals.push_back(t[row][col - 1]); vals.push_back(t[row - 1][col - 1]); std::sort(vals.begin(), vals.end()); treeRect.update(vals[2], vals[3] - 1, 1); } void remL(int row, int col) { // std::cout << "remL: " << row << ' ' << col << '\n' << std::flush; if (row > n || col > m || row == 1 || col == 1) { return; } std::vector <int> vals; vals.push_back(t[row][col]); vals.push_back(t[row - 1][col]); vals.push_back(t[row][col - 1]); vals.push_back(t[row - 1][col - 1]); std::sort(vals.begin(), vals.end()); treeRect.update(vals[2], vals[3] - 1, -1); } void addSingularUp(int row, int col) { int min = std::min(t[row][col], t[row - 1][col]); int max = std::max(t[row][col], t[row - 1][col]); treeLineCol.update(min, max - 1, 1); min = std::min(t[row][col], t[row][col - 1]); max = std::max(t[row][col], t[row][col - 1]); treeLineRow.update(min, max - 1, 1); } void addSingularRect(int row, int col) { std::vector <int> v; v.push_back(t[row - 1][col]); v.push_back(t[row][col - 1]); v.push_back(t[row + 1][col]); v.push_back(t[row][col + 1]); std::sort(v.begin(), v.end()); if (t[row][col] < v[1]) { treeRect.update(std::max(v[0], t[row][col]), v[1] - 1, 1); } } void remSingularRect(int row, int col) { std::vector <int> v; v.push_back(t[row - 1][col]); v.push_back(t[row][col - 1]); v.push_back(t[row + 1][col]); v.push_back(t[row][col + 1]); std::sort(v.begin(), v.end()); if (t[row][col] < v[1]) { treeRect.update(std::max(v[0], t[row][col]), v[1] - 1, -1); } } void addSingular(int row, int col) { int min = std::min(t[row][col], t[row - 1][col]); int max = std::max(t[row][col], t[row - 1][col]); treeLineCol.update(min, max - 1, 1); min = std::min(t[row][col], t[row][col - 1]); max = std::max(t[row][col], t[row][col - 1]); treeLineRow.update(min, max - 1, 1); min = std::min(t[row][col], t[row + 1][col]); max = std::max(t[row][col], t[row + 1][col]); treeLineCol.update(min, max - 1, 1); min = std::min(t[row][col], t[row][col + 1]); max = std::max(t[row][col], t[row][col + 1]); treeLineRow.update(min, max - 1, 1); } void remSingular(int row, int col) { int min = std::min(t[row][col], t[row - 1][col]); int max = std::max(t[row][col], t[row - 1][col]); treeLineCol.update(min, max - 1, -1); min = std::min(t[row][col], t[row][col - 1]); max = std::max(t[row][col], t[row][col - 1]); treeLineRow.update(min, max - 1, -1); min = std::min(t[row][col], t[row + 1][col]); max = std::max(t[row][col], t[row + 1][col]); treeLineCol.update(min, max - 1, -1); min = std::min(t[row][col], t[row][col + 1]); max = std::max(t[row][col], t[row][col + 1]); treeLineRow.update(min, max - 1, -1); } void add(int row, int col) { addL(row, col); addL(row + 1, col); addL(row, col + 1); addL(row + 1, col + 1); addSingular(row, col); addSingularRect(row, col); } void rem(int row, int col) { remL(row, col); remL(row + 1, col); remL(row, col + 1); remL(row + 1, col + 1); remSingular(row, col); remSingularRect(row, col); } void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { n = H; m = W; for (int i = 0 ; i <= n + 1 ; ++i) { t[i].resize(m + 2, n * m + 1); } C.insert(C.begin(), -1); R.insert(R.begin(), -1); for (int &val : R) val++; for (int &val : C) val++; r = R; c = C; treeRow.build(r); treeCol.build(c); for (int i = 1 ; i <= n * m ; ++i) { t[R[i]][C[i]] = i; } treeRect.build(); treeLineRow.build(); treeLineCol.build(); for (int i = 1 ; i <= n ; ++i) { for (int j = 1 ; j <= m ; ++j) { addL(i, j); addSingularUp(i, j); addSingularRect(i, j); } } for (int i = 1 ; i <= m ; ++i) { int min = t[n][i]; int max = n * m + 1; treeLineCol.update(min, max - 1, 1); } for (int i = 1 ; i <= n ; ++i) { int min = t[i][m]; int max = n * m + 1; treeLineRow.update(min, max - 1, 1); } int ans = 0; int pos = 1; if (r[1] == r[2]) { pos = treeRow.search(r[1]); ans = treeLineRow.query(1, pos, 2); } if (c[1] == c[2]) { pos = treeCol.search(c[1]); ans = treeLineCol.query(1, pos, 2); } } int swap_seats(int a, int b) { a++; b++; int rowA = r[a]; int colA = c[a]; int rowB = r[b]; int colB = c[b]; rem(rowA, colA); rem(rowB, colB); std::swap(t[rowA][colA], t[rowB][colB]); std::swap(c[a], c[b]); std::swap(r[a], r[b]); treeRow.update(a, r[a]); treeRow.update(b, r[b]); treeCol.update(a, c[a]); treeCol.update(b, c[b]); add(rowA, colA); add(rowB, colB); int ans = 0; int pos = 1; if (r[1] == r[2]) { pos = treeRow.search(r[1]); ans = treeLineRow.query(1, pos, 2); } if (c[1] == c[2]) { pos = treeCol.search(c[1]); ans = treeLineCol.query(1, pos, 2); } if (pos < n * m) { ans += treeRect.query(pos + 1, n * m, 0); } return ans; }

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

seats.cpp: In member function 'void SegmentTreeLazy::build(int, int, int)':
seats.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeLazy::update(int, int, int, int, int, int)':
seats.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'SegmentTreeLazy::Node SegmentTreeLazy::query(int, int, int, int, int)':
seats.cpp:99:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeMinMax::build(int, int, int, std::vector<int>&)':
seats.cpp:158:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  158 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeMinMax::update(int, int, int, int, int)':
seats.cpp:172:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'int SegmentTreeMinMax::search(int, int, int, int)':
seats.cpp:186:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:400:9: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  400 |     int ans = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...