Submission #1060581

#TimeUsernameProblemLanguageResultExecution timeMemory
1060581woodSeats (IOI18_seats)C++17
5 / 100
4097 ms135012 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> p32; typedef pair<ll,ll> p64; #define pb push_back #define eb emplace_back #define fi first #define se second #define vi vector<int> #define vp32 vector<p32> #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define MOD %1000000007 #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //never guess //never debug without reviewing code //never try adding ones or substracting them //only step by step debug when necessay constexpr int N = 3e6; struct segtree{ int size = 1, xmin[N], xmax[N], ymin[N],ymax[N]; segtree(int n){ while(size<n) size*=2; fill(xmin,xmin+N,INT_MAX); fill(xmax,xmax+N,0); fill(ymin,ymin+N,INT_MAX); fill(ymax,ymax+N,0); } void set(int i, int xx, int yy){ set(i,xx,yy,0,0,size); } void set(int i, int xx, int yy, int x, int lx, int rx){ if(rx-lx==1){ xmin[x]=xmax[x]=xx; ymin[x]=ymax[x]=yy; return; } int m = (lx+rx)/2; if(i<m)set(i,xx,yy,2*x+1,lx,m); else set(i,xx,yy,2*x+2,m,rx); xmin[x] = min(xmin[2*x+1],xmin[2*x+2]); ymin[x] = min(ymin[2*x+1],ymin[2*x+2]); xmax[x] = max(xmax[2*x+1],xmax[2*x+2]); ymax[x] = max(ymax[2*x+1],ymax[2*x+2]); } vi get(int l ,int r){ return get(l,r,0,0,size); } vi get(int l, int r, int x, int lx, int rx){ if(lx>=r||rx<=l)return vi({INT_MAX,0,INT_MAX,0}); else if(lx>=l&&rx<=r)return vi({xmin[x],xmax[x],ymin[x],ymax[x]}); int m = (rx+lx)/2; vi a = get(l,r,2*x+1,lx,m), b = get(l,r,2*x+2,m,rx); return vi({min(a[0],b[0]),max(a[1],b[1]),min(a[2],b[2]), max(a[3],b[3])}); } }; vi xs, ys; segtree sgt(1); void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { sgt = segtree(H*W); for(int i = 0; i<H*W; i++){ xs.pb(R[i]); ys.pb(C[i]); sgt.set(i,xs[i],ys[i]); } } int swap_seats(int a, int b) { int cur = 1; swap(xs[a],xs[b]); swap(ys[a],ys[b]); sgt.set(a,xs[a],ys[a]); sgt.set(b,xs[b],ys[b]); int cnt = 0; while(cur<=xs.size()){ vi v = sgt.get(0,cur); if((v[1]-v[0]+1)*(v[3]-v[2]+1)==cur){ cnt++; cur++; } else cur =(v[1]-v[0]+1)*(v[3]-v[2]+1); } return cnt; }

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while(cur<=xs.size()){
      |           ~~~^~~~~~~~~~~
#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...