(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 #328600

#TimeUsernameProblemLanguageResultExecution timeMemory
328600figter001Seats (IOI18_seats)C++17
100 / 100
3379 ms193796 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; vector<vector<int>> loc,d; vector<pair<int,int>> at; const vector<pair<int,int>> dir = {{0,0},{0,1},{1,0},{1,1}}; const vector<vector<int>> X = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}}; struct node{ node *l,*r; int lazy,mn,cnt; node(){ l = r = NULL; mn = 1e9; lazy = 0; cnt = 1; } void pro(){ mn += lazy; if(l != NULL)l->lazy += lazy; if(r != NULL)r->lazy += lazy; lazy = 0; } void marge(){ if(l->mn < r->mn){ mn = l->mn; cnt = l->cnt; }else if(r->mn < l->mn){ mn = r->mn; cnt = r->cnt; }else if(l->mn == r->mn){ mn = l->mn; cnt = l->cnt + r->cnt; } } }; int n; node *head; void update(int at,int val,node *&n = head,int s = 1,int e = ::n){ if(n == NULL)n = new node(); if(s > at || e < at)return; if(s == e){ n->mn = val; n->cnt = 1; return; } update(at , val , n->l , s , (s+e)/2); update(at , val , n->r , (s+e)/2+1 , e); n->marge(); // cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n'; } void update_range(int l,int r,int val,node *&n = head,int s = 1,int e = ::n){ n->pro(); if(s > r || e < l || l > r)return; if(s >= l && e <= r){ n->lazy += val; n->pro(); return; } update_range(l , r , val , n->l , s , (s+e)/2); update_range(l , r , val , n->r , (s+e)/2+1 , e); n->marge(); // cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n'; } /* pair<int,int> get(int l,int r,node *& n = head,int s = 1,int e = ::n){ n->pro(); if(n == NULL)return {1e9,0}; if(s > r || e < l || l > r)return {1e9,0}; if(s >= l && e <= r)return {n->mn,n->cnt}; pair<int,int> a = get(l , r , n->l , s , (s+e) / 2); pair<int,int> b = get(l , r , n->r , (s+e)/2+1 , e); if(a.first < b.first)return a; else if(a.first > b.first)return b; else{ return {a.first , a.second + b.second}; } } */ int h,w; bool good(int i,int j){ if(i < 0 || j < 0 || i >= h || j >= w)return false; return true; } int getd(int i,int j,int x){ if(!good(i,j) || loc[i][j] > x)return 0; return 1; } int getv(int a){ return d[a][2] - d[a][3] + d[a][0] - d[a][1]; } void add(int l,int r,int v){ update_range(l,r,v); } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { bool v = false; if(H > W){ v = true; swap(H,W); } h = H;w = W; n = H*W; at = vector<pair<int,int>>(n); d.resize(n,vector<int>(4)); loc.resize(H,vector<int>(W)); head = new node(); for(int i=0;i<n;i++){ if(v)swap(R[i],C[i]); at[i] = {R[i] , C[i]}; loc[R[i]][C[i]] = i; } int sum = 0; for(int i=0;i<n;i++){ for(int j=0;j<4;j++){ int x = at[i].first + dir[j].first; int y = at[i].second + dir[j].second; int w = getd(x-1,y-1,i) + getd(x-1,y,i) + getd(x,y-1,i) + getd(x,y,i); d[i][w-1]++; } sum += getv(i); // cerr << sum << '\n'; // cerr << i << " : "; // for(int j=1;j<=4;j++){ // cerr << d[i][j] << ' '; // } // cerr << '\n'; update(i + 1 , sum); } // cerr << head->mn << ' ' << head->cnt << '\n'; // cerr << '\n'; return; } int swap_seats(int a, int b) { swap(at[a] , at[b]); swap(loc[at[a].first][at[a].second] , loc[at[b].first][at[b].second]); int A = a,B = b; // cerr << "MN : " << get(1,n).first << ' ' << get(1,n).second << '\n'; for(vector<int> i : X){ // cerr << a << ' ' << b << '\n'; int ai = at[A].first + i[0]; int aj = at[A].second + i[1]; if(good(ai,aj)){ int a = loc[ai][aj]; add(a+1 , n , -getv(a)); // cerr << "A : " << a << '\n'; // cerr << getv(a) << ' '; d[a] = {0,0,0,0}; for(int j=0;j<4;j++){ int x = ai + dir[j].first; int y = aj + dir[j].second; int w = getd(x-1,y-1,a) + getd(x-1,y,a) + getd(x,y-1,a) + getd(x,y,a); d[a][w-1]++; } add(a+1 , n , getv(a)); // cerr << getv(a) << '\n'; // for(int j=1;j<=4;j++) // cerr << d[a][j] << ' '; // cerr << '\n'; } int bi = at[B].first + i[0]; int bj = at[B].second + i[1]; if(good(bi,bj)){ int b = loc[bi][bj]; add(b+1 , n , -getv(b)); // cerr << "B : " << b << '\n'; // cerr << getv(b) << ' '; d[b] = {0,0,0,0}; for(int j=0;j<4;j++){ int x = bi + dir[j].first; int y = bj + dir[j].second; int w = getd(x-1,y-1,b) + getd(x-1,y,b) + getd(x,y-1,b) + getd(x,y,b); d[b][w-1]++; } add(b+1 , n , getv(b)); // cerr << getv(b) << '\n'; // for(int j=1;j<=4;j++) // cerr << d[b][j] << ' '; // cerr << '\n'; } // cerr << "WTF : " << get(1,n-1).first << ' ' << get(1,n-1).second << '\n'; // cerr << "mn : " << get(1,n).first << ' ' << get(1,n).second << '\n'; } // cerr << head->mn << ' ' << head->cnt << '\n'; // cerr << get(n,n).first << '\n'; return head->cnt; }
#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...