제출 #414617

#제출 시각아이디문제언어결과실행 시간메모리
414617_fractal자리 배치 (IOI18_seats)C++17
100 / 100
2464 ms128608 KiB
#include "seats.h" #include <iostream> #include <climits> #include <algorithm> using namespace std; #define pb push_back #define s second #define f first typedef pair<int, int> pii; const int n = 1e6 + 200; const int inf = (1 << 30); const int dx[] = {0, -1, 0, -1}; const int dy[] = {0, 0, -1, -1}; int s, ans = 0; int h, w; int cur[4]; int **val, **was; int dd[n]; pii pos[n]; struct tree_line { int t[n << 2], p[n << 2]; int cnt[n << 2]; void push(int v, int tl, int tr) { if (p[v] != 0) { if (tl != tr) { p[v * 2] += p[v]; p[v * 2 + 1] += p[v]; } t[v] += p[v]; p[v] = 0; } } void build(int v = 1, int tl = 1, int tr = s) { if (tl == tr) { t[v] = dd[tl]; cnt[v] = 1; return; } int tm = tl + tr >> 1; build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr); t[v] = min(t[v << 1], t[v << 1 | 1]); cnt[v] = 0; if (t[v] == t[v << 1]) cnt[v] += cnt[v << 1]; if (t[v] == t[v << 1 | 1]) cnt[v] += cnt[v << 1 | 1]; } void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = s) { if (l > r) return; push(v, tl, tr); if (l <= tl && tr <= r) { p[v] += val; push(v, tl, tr); return; } if (r < tl || tr < l) return; int tm = tl + tr >> 1; upd(l, r, val, v * 2, tl, tm); upd(l, r, val, v * 2 + 1, tm + 1, tr); t[v] = min(t[v * 2], t[v * 2 + 1]); cnt[v] = 0; if (t[v] == t[v * 2]) cnt[v] += cnt[v * 2]; if (t[v] == t[v * 2 + 1]) cnt[v] += cnt[v * 2 + 1]; } int get() { return cnt[1]; } } t; void del(int _x, int _y) { for (int j = 0, x, y; j < 4; ++j) { x = _x - dx[j]; y = _y - dy[j]; if (was[x][y]) continue; was[x][y] = 1; for (int i = 0; i < 4; ++i) cur[i] = val[x + dx[i]][y + dy[i]]; sort(cur, cur + 4); t.upd(cur[0], cur[1] - 1, -1); t.upd(cur[2], cur[3] - 1, -5); } } void add(int _x, int _y) { for (int j = 0, x, y; j < 4; ++j) { x = _x - dx[j]; y = _y - dy[j]; if (was[x][y]) continue; was[x][y] = 1; for (int i = 0; i < 4; ++i) cur[i] = val[x + dx[i]][y + dy[i]]; sort(cur, cur + 4); t.upd(cur[0], cur[1] - 1, +1); t.upd(cur[2], cur[3] - 1, +5); } } void clr(int _x, int _y) { for (int j = 0, x, y; j < 4; ++j) { x = _x - dx[j]; y = _y - dy[j]; was[x][y] = 0; } } void give_initial_chart(int _h, int _w, vector<int> r, vector<int> c) { h = _h, w = _w; s = h * w; val = new int*[h + 5]; was = new int*[h + 5]; for (int i = 0; i <= h + 3; ++i) { val[i] = new int[w + 5]; was[i] = new int[w + 5]; } for (int i = 1; i <= s; ++i) { c[i - 1]++, r[i - 1]++; pos[i] = {r[i - 1], c[i - 1]}; val[r[i - 1]][c[i - 1]] = i; } for (int i = 0; i <= w + 1; ++i) val[0][i] = val[h + 1][i] = s + 1; for (int i = 0; i <= h + 1; ++i) val[i][0] = val[i][w + 1] = s + 1; for (int i = 1; i <= h + 1; ++i) { for (int j = 1; j <= w + 1; ++j) { clr(i, j); for (int k = 0; k < 4; ++k) cur[k] = val[i + dx[k]][j + dy[k]]; sort(cur, cur + 4); dd[cur[0]] += 1; dd[cur[1]] -= 1; dd[cur[2]] += 5; dd[cur[3]] -= 5; } } for (int i = 1; i <= s; ++i) dd[i] += dd[i - 1]; t.build(); return; } int swap_seats(int a, int b) { ++a, ++b; del(pos[a].f, pos[a].s); del(pos[b].f, pos[b].s); clr(pos[a].f, pos[a].s); clr(pos[b].f, pos[b].s); swap(pos[a], pos[b]); val[pos[a].f][pos[a].s] = a; val[pos[b].f][pos[b].s] = b; add(pos[a].f, pos[a].s); add(pos[b].f, pos[b].s); clr(pos[a].f, pos[a].s); clr(pos[b].f, pos[b].s); return t.get(); }

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

seats.cpp: In member function 'void tree_line::build(int, int, int)':
seats.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
seats.cpp: In member function 'void tree_line::upd(int, int, int, int, int, int)':
seats.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
#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...