Submission #98316

#TimeUsernameProblemLanguageResultExecution timeMemory
98316fefeSeats (IOI18_seats)C++17
5 / 100
4090 ms227932 KiB
#include "seats.h" #include<bits/stdc++.h> #define MAX_N 1000005 #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second using namespace std; typedef pair<int,int> pii; int h,w; std::vector<int> r; set<int> X[MAX_N],Y[MAX_N]; pii V[MAX_N]; vector<int> lst; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { int i; h=H;w=W; for(i=0;i<H*W;i++){ V[i]={R[i],C[i]}; X[R[i]].insert(i); Y[C[i]].insert(i); } } int swap_seats(int a, int b) { int i; X[V[a].fi].erase(a);Y[V[a].se].erase(a); X[V[b].fi].erase(b);Y[V[b].se].erase(b); swap(V[a],V[b]); X[V[a].fi].insert(a);Y[V[a].se].insert(a); X[V[b].fi].insert(b);Y[V[b].se].insert(b); lst.clear();lst.resize(0); for(i=0;i<h;i++) lst.pb(*X[i].begin()); for(i=0;i<w;i++) lst.pb(*Y[i].begin()); sort(all(lst));lst.erase(unique(all(lst)),lst.end()); pii x,y; int ans=1; x={V[0].fi,V[0].fi};y={V[0].se,V[0].se}; for(int p:lst){ ans+=((x.se-x.fi+1)*(y.se-y.fi+1)==(p)); y.fi=min(y.fi,V[p].se);y.se=max(y.se,V[p].se); x.fi=min(x.fi,V[p].fi);x.se=max(x.se,V[p].fi); } return ans; }
#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...