Submission #115562

#TimeUsernameProblemLanguageResultExecution timeMemory
115562WhipppedCreamSeats (IOI18_seats)C++17
0 / 100
4085 ms56796 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 1e6+5; int r[maxn], c[maxn]; int n, m; struct node { int mnr, mxr; int mnc, mxc; node(){} node(int a, int b, int c, int d) : mnr(a), mxr(b), mnc(c), mxc(d) {} bool operator == (node other) const { if(mnr != other.mnr) return false; if(mnc != other.mnc) return false; if(mxr != other.mxr) return false; if(mxc != other.mxc) return false; return true; } }; bool in(node x, node y) { return y.mnr<= x.mnr && y.mnc<= x.mnc && x.mxr<= y.mxr && x.mxc<= y.mxc; } node st[4*maxn]; node pull(node &x, node &y) { return node(min(x.mnr, y.mnr), max(x.mxr, y.mxr), min(x.mnc, y.mnc), max(x.mxc, y.mxc)); } void update(int x, int dr, int dc, int p = 1, int L = 0, int R = n*m-1) { if(L == R) { st[p] = node(dr, dr, dc, dc); return; } int M = (L+R)/2; if(x<= M) update(x, dr, dc, 2*p, L, M); else update(x, dr, dc, 2*p+1, M+1, R); st[p] = pull(st[2*p], st[2*p+1]); } node ask(int i, int j, int p = 1, int L = 0, int R = n*m-1) { if(i> R || j< L) return node(1e9, 0, 1e9, 0); if(i<= L && R<= j) return st[p]; int M = (L+R)/2; node x = ask(i, j, 2*p, L, M); node y = ask(i, j, 2*p+1, M+1, R); return pull(x, y); } int border(node &x, int p = 1, int L = 0, int R = n*m-1) { if(L == R) { if(in(st[p], x)) return L; return L-1; } node here = st[2*p]; int M = (L+R)/2; if(in(st[p], x)) return border(x, 2*p+1, M+1, R); return border(x, 2*p, L, M); } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = H; m = W; for(int i = 0; i< n*m; i++) { r[i] = R[i]; c[i] = C[i]; update(i, r[i], c[i]); } } int swap_seats(int a, int b) { update(a, r[b], c[b]); update(b, r[a], c[a]); swap(r[a], r[b]); swap(c[a], c[b]); int st = 0; int ans = 0; int cnt = 0; while(st< n*m) { node x = ask(0, st); int lo = border(x); int sz = (x.mxr-x.mnr+1)*(x.mxc-x.mnc+1); ans += st+1<= sz && sz<= lo+1; st = lo+1; cnt++; } // printf("incremented %d times\n", cnt); return ans; }

Compilation message (stderr)

seats.cpp: In function 'int border(node&, int, int, int)':
seats.cpp:73:7: warning: variable 'here' set but not used [-Wunused-but-set-variable]
  node here = st[2*p];
       ^~~~
#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...