| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1037435 | aaaaaarroz | Seats (IOI18_seats) | C++17 | 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>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF = 1e9;
int n, m;
struct SegmentTreeLazy{
struct Node{
int min;
int cnt;
int lazy;
Node(){
min = cnt = lazy = 0;
}
friend Node operator + (const Node &left, const Node &right){
Node res;
res.min = std::min(left.min, right.min);
if (res.min == left.min) res.cnt += left.cnt;
if (res.min == right.min) res.cnt += right.cnt;
return res;
}
};
Node tree[4*MAXN];
void build(int l, int r, int node){
if (l == r){
tree[node].min = 0;
tree[node].cnt = 1;
return;
}
int mid = l + r >> 1;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = tree[2*node] + tree[2*node + 1];
}
void push(int node, int l, int r){
if (tree[node].lazy == 0){
return;
}
tree[node].min += tree[node].lazy;
if (l < r){
tree[2*node].lazy += tree[node].lazy;
tree[2*node + 1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
void update(int l, int r, int node, int queryL, int queryR, int queryVal){
push(node, l, r);
if (queryR < l || r < queryL){
return;
}
if (queryL <= l && r <= queryR){
tree[node].lazy = queryVal;
push(node, l, r);
return;
}
int mid = l + r >> 1;
update(l, mid, 2*node, queryL, queryR, queryVal);
update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
tree[node] = tree[2*node] + tree[2*node + 1];
}
Node query(int l, int r, int node, int queryL, int queryR){
push(node, l, r);
if (queryL <= l && r <= queryR){
return tree[node];
}
Node res; res.min = INF;
int mid = l + r >> 1;
if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
void build(){
build(1, n * m, 1);
}
void update(int l, int r, int val){
update(1, n * m, 1, l, r, val);
}
int query(int l, int r){
Node res = query(1, n * m, 1, l, r);
return res.cnt;
}
};
SegmentTreeLazy tree;
std::vector <int> t[MAXN];
std::vector <int> row, col;
void add(int idx){
tree.update(std::min(t[1][idx], t[1][idx - 1]), std::max(t[1][idx], t[1][idx - 1]) - 1, 1);
}
void rem(int idx){
tree.update(std::min(t[1][idx], t[1][idx - 1]), std::max(t[1][idx], t[1][idx - 1]) - 1, -1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
n = H;
m = W;
for (int i = 1 ; i <= n + 1 ; ++i){
t[i].resize(m + 2, n * m + 1);
}
C.insert(C.begin(), -1);
R.insert(R.begin(), -1);
for (int &val : R) val++;
for (int &val : C) val++;
row = R; col = C;
for (int i = 1 ; i <= n * m ; ++i){
t[R[i]][C[i]] = i;
}
tree.build();
for (int i = 1 ; i <= m + 1 ; ++i){
add(i);
}
}
int swap_seats(int a, int b){
a++; b++;
int posA = col[a];
int posB = col[b];
assert(t[1][posA] == a);
assert(t[1][posB] == b);
rem(posA);
rem(posB);
rem(posA + 1);
rem(posB + 1);
swap(t[1][posA], t[1][posB]);
swap(col[a], col[b]);
add(posA);
add(posB);
add(posA + 1);
add(posB + 1);
return tree.query(1, n * m);
}