제출 #245745

#제출 시각아이디문제언어결과실행 시간메모리
245745mikoarm자리 배치 (IOI18_seats)C++14
25 / 100
4081 ms69940 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; struct Tree { vector<int> mins, maxs; int B; Tree(){} Tree(vector<int> R) { B = 1; while (B < (int)R.size()) { B *= 2; } maxs.resize(2*B), mins.resize(2*B); for (int i = B; i < B + (int)R.size(); i++) mins[i] = R[i-B], maxs[i] = R[i-B]; for (int i = B-1; i >= 1; i--) maxs[i] = max(maxs[2*i], maxs[2*i+1]), mins[i] = min(mins[2*i], mins[2*i+1]); } pair<int,int> query(int a, int b) { a += B; b += B; pair<int,int> ret = {max(maxs[a], maxs[b]), min(maxs[a], maxs[b])}; while (a / 2 != b / 2) { if (a % 2 == 0) ret.first = max(ret.first, maxs[a+1]), ret.second = min(ret.second, mins[a+1]); if (b % 2 == 1) ret.first = max(ret.first, maxs[b-1]), ret.second = min(ret.second, mins[b-1]); a /= 2; b /= 2; } return ret; } void update(int a) { a += B; a /= 2; while (a > 0) { maxs[a] = max(maxs[2*a], maxs[2*a+1]); mins[a] = min(mins[2*a], mins[2*a+1]); a /= 2; } } }; int H, W; Tree tree_r, tree_c; int B; void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) { H = _H; W = _W; tree_r = Tree(R); tree_c = Tree(C); B = tree_r.B; } int swap_seats(int a, int b) { swap(tree_r.maxs[a+B], tree_r.maxs[b+B]); swap(tree_r.mins[a+B], tree_r.mins[b+B]); swap(tree_c.maxs[a+B], tree_c.maxs[b+B]); swap(tree_c.mins[a+B], tree_c.mins[b+B]); tree_r.update(a); tree_r.update(b); tree_c.update(a); tree_c.update(b); //puts("swapped"); int ret = 0; for (int i = 0; i < H*W; i++) { int rmax, rmin, cmax, cmin; tie(rmax, rmin) = tree_r.query(0,i); tie(cmax, cmin) = tree_c.query(0,i); /*printf("i: %d\n", i); printf("rmax: %d\n", rmax); printf("rmin: %d\n", rmin); printf("cmax: %d\n", cmax); printf("cmin: %d\n", cmin);*/ int area = (rmax-rmin+1)*(cmax-cmin+1); ret += (area == i+1); if (area > i+1) i = area-2; } return ret; }
#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...