Submission #294406

#TimeUsernameProblemLanguageResultExecution timeMemory
294406zoooma13Seats (IOI18_seats)C++14
0 / 100
444 ms76544 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; #define MAX_N 1000006 #define pii pair<int ,int> #define mxp first #define mip second #define FL p<<1 #define FR p<<1|1 int n; int h ,w ,ans; pii tree[4*MAX_N][2]; vector <int> cor[2] ,sat; pii mrg(pii x ,pii y){ return {max(x.mxp ,y.mxp) ,min(x.mip ,y.mip)}; } void bld(int l=0 ,int r=n-1 ,int p=1){ if(l == r){ tree[p][0] = {cor[0][l] ,cor[0][l]}; tree[p][1] = {cor[1][l] ,cor[1][l]}; return; } int mid = (l+r)>>1; bld(l ,mid ,FL); bld(mid+1 ,r ,FR); tree[p][0] = mrg(tree[FL][0] ,tree[FR][0]); tree[p][1] = mrg(tree[FL][1] ,tree[FR][1]); } void upd(int i ,int l=0 ,int r=n-1 ,int p=1){ if(l == r){ tree[p][0] = {cor[0][l] ,cor[0][l]}; tree[p][1] = {cor[1][l] ,cor[1][l]}; return; } int mid = (l+r)>>1; if(i <= mid) upd(i ,l ,mid ,FL); else upd(i ,mid+1 ,r ,FR); tree[p][0] = mrg(tree[FL][0] ,tree[FR][0]); tree[p][1] = mrg(tree[FL][1] ,tree[FR][1]); } pair<pii ,pii> qry(int qr ,int l=0 ,int r=n-1 ,int p=1){ if(qr < l) return {{-1e9 ,1e9} ,{-1e9 ,1e9}}; if(r <= qr) return {tree[p][0] ,tree[p][1]}; int mid = (l+r)>>1; auto lf = qry(qr ,l ,mid ,FL); auto rt = qry(qr ,mid+1 ,r ,FR); return {mrg(lf.first ,rt.first) ,mrg(lf.second ,rt.second)}; } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = R.size(); h = H; w = W; sat.resize(n); cor[0] = R; cor[1] = C; bld(); int mxR = 0 ,miR = H; int mxC = 0 ,miC = W; for(int i=0; i<R.size(); i++){ mxR = max(mxR ,R[i]); miR = min(miR ,R[i]); mxC = max(mxC ,C[i]); miC = min(miC ,C[i]); if((mxR-miR+1)*(mxC-miC+1) == i+1) sat[i] = 1 ,ans++; } } int swap_seats(int a, int b) { swap(cor[0][a] ,cor[0][b]); swap(cor[1][a] ,cor[1][b]); upd(a) ,upd(b); if(b-a <= 10000){ auto x = qry(a); int mxR = x.first.mxp ,miR = x.first.mip; int mxC = x.second.mxp ,miC = x.second.mip; for(int i=a; i<=b; i++){ mxR = max(mxR ,cor[0][i]); miR = min(miR ,cor[0][i]); mxC = max(mxC ,cor[1][i]); miC = min(miC ,cor[1][i]); if((mxR-miR+1)*(mxC-miC+1) == i+1){ if(!sat[i]){ sat[i] = 1 ,ans++; } }else{ if(sat[i]){ sat[i] = 0 ,ans--; } } } }else{ } return ans; }

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0; i<R.size(); i++){
      |                  ~^~~~~~~~~
#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...