(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #170711

#TimeUsernameProblemLanguageResultExecution timeMemory
170711oolimrySeats (IOI18_seats)C++14
100 / 100
2625 ms136904 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; const long long inf = 1e9; typedef pair<long long, int> ii; int n, rows, cols; static ii pos[1000005]; ///for each number, ii(r, c) static vector<vector<int> > arr; ///arr[r*cols+c] is the element at (r,c) ///we build a grid such that the boundaries are filled with the number n ///Everything here onwards is segment tree ///This is a range min range add segment tree, but we also store the no. of occurances of the minimum element static ii tree[2000005]; ///we store the minimum element, and the number of occurances static long long lazy[2000005]; ///helper function to update the value of node i from the children of i inline void relax(int i){ if(tree[i<<1].first == tree[i<<1|1].first){ tree[i] = ii(tree[i<<1].first+lazy[i], tree[i<<1].second + tree[i<<1|1].second); } else{ tree[i] = min(tree[i<<1],tree[i<<1|1]); tree[i].first += lazy[i]; } } void initSegment(){ for(int i = n;i < 2 * n;i++) tree[i] = ii(0,1); for(int i = n - 1;i >= 0;i--) relax(i); } inline void update(int l, int r, long long v){ if(l == r) return; int ll = l + n, rr = r - 1 + n; for(l += n,r += n;l < r;l>>=1,r>>=1){ if(l&1){ tree[l].first += v; lazy[l] += v; l++; } if(r&1){ r--; tree[r].first += v; lazy[r] += v; } } while(ll > 1){ ll >>= 1; relax(ll); } while(rr > 1){ rr >>= 1; relax(rr); } } inline int query(){ if(tree[1].first+lazy[1] == 4){ return tree[1].second; } else{ return 0; } } ///segment tree ends ///consider a 2x2 square whose top-left corner is at r, c void makeUpdate(int r, int c, bool isUndo){ vector<int> values = {arr[r][c],arr[r+1][c],arr[r][c+1],arr[r+1][c+1]}; sort(values.begin(),values.end()); ///if isReverse, we undo our previous update if(isUndo){ update(values[0],values[1],-1); update(values[2],values[3],-inf); } else{ update(values[0],values[1],1); ///add one to imply within that range, there is one more 2x2 square with exactly 1 black square update(values[2],values[3],inf); ///add infinity to "ruin" that range. When there are 2 black squares in the 2x2 square, it's impossible to have beautiful rectangle } } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = H * W; rows = H; cols = W; for(int i = 0;i < rows+2;i++){ arr.push_back({}); arr.back().assign(cols+2,n); } for(int i = 0;i < n;i++){ R[i]++; C[i]++; arr[R[i]][C[i]] = i; pos[i] = ii(R[i],C[i]); } initSegment(); for(int r = 0;r <= rows;r++){ for(int c = 0;c <= cols;c++){ makeUpdate(r,c,false); } } } int swap_seats(int a, int b) { ii aPos = pos[a]; ii bPos = pos[b]; ///undo updates for all affected rectangles makeUpdate(aPos.first-1,aPos.second-1,true); makeUpdate(aPos.first,aPos.second-1,true); makeUpdate(aPos.first-1,aPos.second,true); makeUpdate(aPos.first,aPos.second,true); makeUpdate(bPos.first-1,bPos.second-1,true); makeUpdate(bPos.first,bPos.second-1,true); makeUpdate(bPos.first-1,bPos.second,true); makeUpdate(bPos.first,bPos.second,true); ///swapping the elements pos[b] = aPos; pos[a] = bPos; arr[aPos.first][aPos.second] = b; arr[bPos.first][bPos.second] = a; ///now update again for all affected rectangles makeUpdate(aPos.first-1,aPos.second-1,false); makeUpdate(aPos.first,aPos.second-1,false); makeUpdate(aPos.first-1,aPos.second,false); makeUpdate(aPos.first,aPos.second,false); makeUpdate(bPos.first-1,bPos.second-1,false); makeUpdate(bPos.first,bPos.second-1,false); makeUpdate(bPos.first-1,bPos.second,false); makeUpdate(bPos.first,bPos.second,false); return query(); }
#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...