제출 #419231

#제출 시각아이디문제언어결과실행 시간메모리
419231peuch자리 배치 (IOI18_seats)C++17
5 / 100
4086 ms86740 KiB
#include "seats.h" #include<bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10; const int MAXW = 1e3 + 10; struct node{ int minx, maxx, miny, maxy; node(int _minx = MAXN, int _maxx = -1, int _miny = MAXN, int _maxy = -1){ minx = _minx; maxx = _maxx; miny = _miny; maxy = _maxy; } node operator + (node a){ node ret; ret.minx = min(minx, a.minx); ret.maxx = max(maxx, a.maxx); ret.miny = min(miny, a.miny); ret.maxy = max(maxy, a.maxy); return ret; } void print(){ printf("%d %d %d %d\n", minx, maxx, miny, maxy); } }; vector<int> r, c; int h, w; node seg[4 * MAXN]; void build(int pos, int ini, int fim); void update(int pos, int ini, int fim, int id, node val); node query(int pos, int ini, int fim, int p, int q); void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { r = R, c = C; h = H, w = W; build(1, 0, h * w - 1); } int swap_seats(int a, int b) { swap(r[a], r[b]); swap(c[a], c[b]); update(1, 0, h * w - 1, a, node(r[a], r[a], c[a], c[a])); update(1, 0, h * w - 1, b, node(r[b], r[b], c[b], c[b])); int ret = 0; for (int i = 0; i < h*w; ){ node val = query(1, 0, h*w-1, 0, i); int mn_x = val.minx, mx_x = val.maxx, mn_y = val.miny, mx_y = val.maxy; if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1) ret++; i = max(i+1, (mx_x-mn_x+1)*(mx_y-mn_y+1)-1); } return ret; } void build(int pos, int ini, int fim){ if(ini == fim){ seg[pos] = node(r[ini], r[ini], c[ini], c[ini]); return; } int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1; build(e, ini, mid); build(d, mid + 1, fim); seg[pos] = seg[e] + seg[d]; } void update(int pos, int ini, int fim, int id, node val){ if(ini > id || fim < id) return; if(ini == fim){ seg[pos] = val; return; } int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1; update(e, ini, mid, id, val); update(d, mid + 1, fim, id, val); seg[pos] = seg[e] + seg[d]; } node query(int pos, int ini, int fim, int p, int q){ if(ini > q || fim < p) return node(); if(ini >= p && fim <= q) return seg[pos]; int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1; return query(e, ini, mid, p, q) + query(d, mid + 1, fim, p, q); }
#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...