| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 91772 | Retro3014 | 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 <vector>
#include <algorithm>
#include <iostream>
#include <deque>
#include <unordered_map>
using namespace std;
#define MAX_N 1000000
#define INF 1000000000
typedef long long ll;
struct S{
int x, y;
};
int h, w, N;
struct T{
int lazy;
int ans, mini;
int s, e;
int l, r;
};
vector<T> seg(1);
vector<S> v;
vector<int> r;
vector<S> s, e;
int ans;
vector<vector<int>> arr;
int tp=1;
void init(int x){
if(seg[x].s!=seg[x].e){
if(seg[x].l==-1){
seg[x].l=tp;
seg[tp]={0, (seg[x].s+seg[x].e)/2-seg[x].s+1, 0, seg[x].s, (seg[x].s+seg[x].e)/2, -1, -1};
tp++;
init(tp-1);
}
if(seg[x].r==-1){
seg[x].r=tp;
seg[tp]={0, seg[x].e-(seg[x].s+seg[x].e)/2, 0, (seg[x].s+seg[x].e)/2+1, seg[x].e, -1, -1};
tp++;
init(tp-1);
}
}
}
void update1(int idx){
if(idx==-1) return;
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy;
seg[seg[idx].l].mini += seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].lazy += seg[idx].lazy;
seg[seg[idx].r].mini += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
}
void update2(int idx){
if(idx==-1) return;
if(seg[idx].l==-1 && seg[idx].r==-1) return;
if(seg[idx].l==-1){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[idx].r==-1){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].l].mini;
}
void lazy_u(int idx, int x, int y, int z){
if(idx==-1) return;
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy;
seg[seg[idx].l].mini += seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].lazy += seg[idx].lazy;
seg[seg[idx].r].mini += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
if(seg[idx].s>=x && seg[idx].e<=y){
seg[idx].mini+=z;
seg[idx].lazy+=z; return;
}
if(seg[idx].e<x || seg[idx].s>y) return;
lazy_u(seg[idx].l, x, y, z);
lazy_u(seg[idx].r, x, y, z);
if(seg[idx].l==-1 && seg[idx].r==-1) return;
if(seg[idx].l==-1){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[idx].r==-1){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].l].mini;
}
vector<int> sq;
int dx[4]={-1, -1, 0, 0}, dy[4]={0, -1, 0, -1};
struct bypass{
size_t operator() (int v) const{
return (size_t) v;
}
};
unordered_map<int, int, bypass> mp;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
seg[0]={0, H*W, 0, 0, H*W-1, -1, -1};
seg.resize(2*H*W);
init(0);
N=H*W;
h=H; w=W;
arr.resize(H);
for(int i=0; i<H; i++){
arr[i].resize(W);
}
for(int i=0; i<R.size(); i++){
v.push_back({R[i], C[i]});
arr[R[i]][C[i]]=i;
}
for(int i=0; i<=H; i++){
for(int j=0; j<=W; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<H && j+dy[k]>=0 && j+dy[k]<W){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
//lazy_u(0, sq[k], N, 1);
mp[sq[k]]++;
}else{
mp[sq[k]]--;
//lazy_u(0, sq[k], N, -1);
}
}
}
}
for(unordered_map<int, int>::iterator it = mp.begin(); it!=mp.end(); ++it){
if(it->second!=0) lazy_u(0, it->first, N, it->second);
}
mp.clear();
}
int swap_seats(int a, int b) {
for(int i=v[a].x; i<=v[a].x+1; i++){
for(int j=v[a].y; j<=v[a].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]-=1;
}else{
mp[sq[k]]+=1;
}
}
}
}
for(int i=v[b].x; i<=v[b].x+1; i++){
for(int j=v[b].y; j<=v[b].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]-=1;
//lazy_u(0, sq[k], N, -1);
}else{
mp[sq[k]]+=1;
//lazy_u(0, sq[k], N, 1);
}
}
}
}
S tmp = v[a]; v[a] = v[b]; v[b] = tmp;
arr[v[a].x][v[a].y]=a; arr[v[b].x][v[b].y]=b;
for(int i=v[a].x; i<=v[a].x+1; i++){
for(int j=v[a].y; j<=v[a].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]+=1;
//lazy_u(0, sq[k], N, 1);
}else{
mp[sq[k]]-=1;
//lazy_u(0, sq[k], N, -1);
}
}
}
}
for(int i=v[b].x; i<=v[b].x+1; i++){
for(int j=v[b].y; j<=v[b].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]+=1;
//lazy_u(0, sq[k], N, 1);
}else{
mp[sq[k]]-=1;
//lazy_u(0, sq[k], N, -1);
}
}
}
}
for(unordered_map<int, int>::iterator it = mp.begin(); it!=mp.end(); ++it){
if(it->second !=0) lazy_u(0, it->first, N, it->second);
}
mp.clear();
return seg[0].ans;
}