제출 #138373

#제출 시각아이디문제언어결과실행 시간메모리
138373MoNsTeR_CuBe자리 배치 (IOI18_seats)C++17
5 / 100
4040 ms159864 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; #define int long long inline int min(int &a, int &b){ if(a < b) return a; return b; } inline int max(int &a, int &b){ if(a < b) return b; return a; } struct node{ node *l, *r; pair<int, int> mini; pair<int, int> maxi; void update(){ mini.first = min(l->mini.first, r->mini.first); mini.second = min(l->mini.second, r->mini.second); maxi.first = max(l->maxi.first, r->maxi.first); maxi.second = max(l->maxi.second, r->maxi.second); } }; vector< pair<int, int> > v; void Build(node* root, int left, int right){ if(left == right){ root->maxi.second = root->mini.second = v[left-1].second; root->maxi.first = root->mini.first = v[left-1].first; return; } int mid = (left+right)/2; root->l = new node{NULL,NULL,{0,0},{0,0}}; root->r = new node{NULL,NULL,{0,0},{0,0}}; Build(root->l, left, mid); Build(root->r, mid+1, right); root->update(); } void update(node* root, int left, int right, int index, pair<int, int> p){ if(left > index || right < index) return; if(left == index && right == index){ root->maxi.second = root->mini.second = p.second; root->maxi.first = root->mini.first = p.first; return; } int mid = (left+right)/2; update(root->l, left, mid, index, p); update(root->r, mid+1, right, index, p); root->update(); } tuple<int, int, int, int> query(node* root, int left, int right, int qLeft, int qRight){ if(left > qRight || right < qLeft) return {INT_MAX, INT_MAX, INT_MIN, INT_MIN}; if(left >= qLeft && right <= qRight){ return {root->mini.first, root->mini.second, root->maxi.first, root->maxi.second}; } int mid = (left+right)/2; tuple<int, int, int, int> p = query(root->l, left, mid, qLeft, qRight); tuple<int, int, int, int> q = query(root->r, mid+1, right, qLeft, qRight); return {min(get<0>(p), get<0>(q)), min(get<1>(p), get<1>(q)), max(get<2>(p), get<2>(q)), max(get<3>(p), get<3>(q))}; } int h, w; node* root = new node{NULL,NULL,{0,0},{0,0}}; #undef int void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { #define int long long h = H; w = W; v.resize(h*w); for(int i = 0; i < H*W; i++){ v[i] = make_pair(R[i], C[i]); } Build(root, 1, H*W); } #undef int int swap_seats(int a, int b) { #define int long long update(root, 1, h*w, a+1, v[b]); update(root, 1, h*w, b+1, v[a]); swap(v[b], v[a]); int curr = 1; int ans = 0; while(curr <= h*w){ tuple<int, int, int, int> q = query(root, 1, h*w, 1, curr); pair<int, int> maxi = {get<2>(q), get<3>(q)}; pair<int, int> mini = {get<0>(q), get<1>(q)}; //if(curr == 5) break; if((maxi.first - mini.first + 1)*(maxi.second - mini.second + 1) == curr){ ans++; curr++; }else{ assert((maxi.first - mini.first + 1)*(maxi.second - mini.second + 1) > curr); curr = (maxi.first - mini.first + 1)*(maxi.second - mini.second + 1); } //cout << ans << endl; } return ans; #undef int }
#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...