| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 601962 | idiot123 | Seats (IOI18_seats) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<pair<int, int>> v;
class InfoTree{
private:
int lrSize = 2;
vector<int> minR;
vector<int> maxR;
vector<int> minC;
vector<int> maxC;
void update(int pos, bool up){
minR[pos] = min(minR[2*pos], minR[2*pos+1]);
maxR[pos] = max(maxR[2*pos], maxR[2*pos + 1]);
minC[pos] = min(minC[2*pos], minC[2*pos + 1]);
maxC[pos] = max(maxC[2*pos], maxC[2*pos + 1]);
if(up && pos > 1)update(pos/2, true);
}
//minR, maxR, minC, maxC
array<int, 4> rangeInfo(int a, int b, int l, int r, int pos){
if(b < l || r < a)return {INF, -INF, INF, -INF};
if(a <= l && r <= b){
return {minR[pos], maxR[pos], minC[pos], maxC[pos]};
}else{
int m = (l + r) / 2;
array<int, 4> ans1 = rangeInfo(a, b, l, m, 2*pos);
array<int, 4> ans2 = rangeInfo(a, b, m+1, r, 2*pos + 1);
return {min(ans1[0], ans2[0]), max(ans1[1], ans2[1]), min(ans1[2], ans2[2]), max(ans1[3], ans2[3])};
}
}
public:
InfoTree(){};
resize(vector<pair<int, int>>& v){
while(lrSize < v.size())lrSize *= 2;
minR.resize(2*lrSize, INF); maxR.resize(2*lrSize, -INF);
minC.resize(2*lrSize, INF); maxC.resize(2*lrSize, -INF);
for(int i =0; i < v.size(); i++){
minR[lrSize + i] = maxR[lrSize + i] = v[i].first;
minC[lrSize + i] = maxC[lrSize + i] = v[i].second;
}
for(int j = lrSize - 1; j >= 1; j--)update(j, false);
}
void set(int pos, int r, int c){
pos += lrSize;
minR[pos] = maxR[pos] = r;
minC[pos] = maxC[pos] = c;
update(pos/2, true);
}
array<int, 4> getInfo(int a, int b){
return rangeInfo(a, b, 0, lrSize - 1, 1);
}
};
InfoTree infoTree;
class SumTree{
private:
int lrSize = 2;
vector<int> v;
void update(int pos){
v[pos] = v[2*pos] + v[2*pos + 1];
}
void push(int pos){
if(v[pos] == 0){
v[2*pos] = v[2*pos + 1] = 0;
}
}
void rangeClear(int a, int b, int l, int r, int pos){
if(b < l || r < a)return;
if(a <= l && r <= b){
v[pos] = 0;
}else{
int m = (l + r)/2;
rangeClear(a, b, l, m, 2*pos);
rangeClear(a, b, m+1, r, 2*pos + 1);
}
}
public:
SumTree(){}
void resize(){
while(lrSize < n)lrSize *= 2;
v.resize(2*lrSize, 0);
}
void add(int pos){
pos += lrSize;
vector<int> path;
while(pos >= 1){
path.push_back(pos);
pos /= 2;
}
for(int i = path.size() - 1; i >= 1; i--){
push(path[i]);
}
v[path[0]] = 1;
for(int i = 1; i < path.size(); i++)update(path[i]);
}
int getAns(){
return v[1];
}
void clear(int a, int b){
rangeClear(a, b, 0, lrSize-1, 1);
}
};
SumTree sumTree;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H * W;
v.resize(n);
for(int i = 0; i < n; i++)v[i] = {R[i], C[i]};
infoTree.resize(v);
sumTree.resize();
int current = 0;
while(current < n){
array<int, 4> info = infoTree.getInfo(0, current);
int h = info[1] - info[0] + 1; int w = info[3] - info[2] + 1;
if(h * w == current + 1){
sumTree.add(current);
current += min(h, w);
}else{
current = h * w - 1;
}
}
}
int swap_seats(int a, int b) {
if(a > b)swap(a, b);
sumTree.clear(a, b-1);
pair<int, int> p = v[a];
v[a] = v[b];
v[b] = p;
infoTree.set(a, v[a].first, v[a].second);
infoTree.set(b, v[b].first, v[b].second);
int current = a;
while(current < b){
array<int, 4> info = infoTree.getInfo(0, current);
int h = info[1] - info[0] + 1; int w = info[3] - info[2] + 1;
if(h * w == current + 1){
sumTree.add(current);
current += min(h, w);
}else{
current = h * w - 1;
}
}
return sumTree.getAns();
}