Submission #412427

#	Time	Username	Problem	Language	Result	Execution time	Memory
412427		Ahmadsm2005	Seats (IOI18_seats)	C++14	5 / 100	4111 ms	215748 KiB

seats

#include "seats.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
//#pragma GCC optimize("-Ofast")
using namespace std;
vector<vector<int>>MAT;
struct node{
node* L=nullptr;
node* R=nullptr;
int V,LL,RR;
};
node* ROOT[1001][2];
pair<int,int>MP[1000001];
void upd(node* X,int T,int v){
if((X->LL)==(X->RR)&&(X->LL)==T){
(X->V)=v;
return;
}
else if((X->LL)>T||(X->RR)<T)
return;
if((X->L)==nullptr)
(X->L)=new node,(X->L->RR)=((X->LL)+(X->RR))/2,(X->L->LL)=(X->LL);
if((X->R)==nullptr)
(X->R)=new node,(X->R->LL)=((X->LL)+(X->RR))/2+1,(X->R->RR)=(X->RR);
upd((X->L),T,v),upd((X->R),T,v);
(X->V)=max((X->L->V),(X->R->V));
}
int query(node* X,int L,int R){
if(X==nullptr)
return 0;
if((X->LL)>=L&&(X->RR)<=R){
return(X->V);
}
else if((X->LL)>R||(X->RR)<L)
return 0;
return max(query((X->L),L,R),query((X->R),L,R));
}
int w,h;
int check(int L,int R,int L2,int R2){
if(L==R)
return query(ROOT[L][0],L2,R2);
return query(ROOT[L2][1],L,R);
/*int maxer=0;
for(int i=L;i<=R;i++){
for(int l=L2;l<=R2;l++)
maxer=max(maxer,MAT[i][l]);
}
return maxer;*/
}
int REC(int x1,int x2,int y1,int y2,int MAXER=0){
int MINER=INT_MAX,MINER2=INT_MAX,MINER3=INT_MAX,MINER4=INT_MAX;
int maxer=0;
if(x1)
MINER=check(x1-1,x1-1,y1,y2);
if(x2+1<h)
MINER2=check(x2+1,x2+1,y1,y2);
if(y1)
MINER3=check(x1,x2,y1-1,y1-1);
if(y2+1<w)
MINER4=check(x1,x2,y2+1,y2+1);
int MINER5=min(min(MINER,MINER2),min(MINER3,MINER4));
if(MINER5==INT_MAX)
return 1;
if(MINER5==MINER)
return REC(x1-1,x2,y1,y2,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
else if(MINER5==MINER2)
return REC(x1,x2+1,y1,y2,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
else if(MINER5==MINER3)
return REC(x1,x2,y1-1,y2,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
else if(MINER5==MINER4)
return REC(x1,x2,y1,y2+1,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
}
void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
h=H,w=W;
for(int i=0;i<1001;i++){
node* Q=new node;
node* Q2=new node;
(Q->LL)=0,(Q->RR)=W;
(Q2->LL)=0,(Q2->RR)=H;
ROOT[i][0]=Q,ROOT[i][1]=Q2;
}
MAT.resize(H);
for(int i=0;i<H;i++)
MAT[i].resize(W);
for(int i=0;i<H*W;i++)
MAT[R[i]][C[i]]=i,MP[i]={R[i],C[i]};
for(int i=0;i<H;i++)
for(int l=0;l<W;l++)
upd(ROOT[i][0],l,MAT[i][l]),upd(ROOT[l][1],i,MAT[i][l]);
}
int swap_seats(int a,int b){
swap(MAT[MP[a].first][MP[a].second],MAT[MP[b].first][MP[b].second]);
swap(MP[a],MP[b]);
int x=MP[a].first,y=MP[a].second,x2=MP[b].first,y2=MP[b].second;
upd(ROOT[x][0],y,MAT[x][y]),upd(ROOT[y][1],x,MAT[x][y]);
upd(ROOT[x2][0],y2,MAT[x2][y2]),upd(ROOT[y2][1],x2,MAT[x2][y2]);
return REC(MP[0].first,MP[0].first,MP[0].second,MP[0].second);
}

Compilation message (stderr)

seats.cpp: In function 'int REC(int, int, int, int, int)':
seats.cpp:52:5: warning: unused variable 'maxer' [-Wunused-variable]
   52 | int maxer=0;
      |     ^~~~~
seats.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30