제출 #1014980

#제출 시각아이디문제언어결과실행 시간메모리
1014980hyakup자리 배치 (IOI18_seats)C++17
37 / 100
4029 ms122960 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; vector<int> linha1(maxn, maxn), linha2(maxn, -maxn), coluna1(maxn, maxn), coluna2(maxn, -maxn), marc(maxn); vector<int> i, j; int n, m; int resp; struct Node{ int l1, l2, c1, c2; Node( int l1 = maxn, int l2 = -maxn, int c1 = maxn, int c2 = -maxn ) : l1(l1), l2(l2), c1(c1), c2(c2) {} Node operator + ( Node n ){ return Node( min(l1, n.l1), max(l2, n.l2), min(c1, n.c1), max(c2, n.c2) ); } int area(){ return (l2 - l1 + 1)*(c2 - c1 + 1); } } seg[4*maxn]; void update( int pos, int ini, int fim, int id, int a, int b ){ if( ini == fim ){ seg[pos] = Node(a, a, b, b); return; } int l = 2*pos, r = 2*pos + 1, mid = (ini + fim)/2; if( id <= mid ) update( l, ini, mid, id, a, b ); else update( r, mid + 1, fim, id, a, b ); seg[pos] = seg[l] + seg[r]; } Node query( int pos, int ini, int fim, int ki, int kf ){ if( ki > fim || ini > kf ) return seg[0]; if( ki <= ini && fim <= kf ) return seg[pos]; int l = 2*pos, r = 2*pos + 1, mid = (ini + fim)/2; return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf ); } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { i = R; j = C; n = H, m = W; if( n <= 1000 && m <= 1000 ) for( int k = 0; k < n*m; k++ ) update( 1, 0, n*m - 1, k, i[k], j[k] ); else{ for( int k = 1; k <= H*W; k++ ){ linha1[k] = min(linha1[k - 1], i[k - 1] ); linha2[k] = max(linha2[k - 1], i[k - 1] ); coluna1[k] = min(coluna1[k - 1], j[k - 1] ); coluna2[k] = max(coluna2[k - 1], j[k - 1] ); if( (linha2[k] - linha1[k] + 1)*(coluna2[k] - coluna1[k] + 1) == k ){ marc[k] = 1; resp++; } } } } int swap_seats(int a, int b) { swap( i[a], i[b] ); swap( j[a], j[b] ); if( n <= 1000 && m <= 1000 ){ update( 1, 0, n*m - 1, a, i[a], j[a] ); update( 1, 0, n*m - 1, b, i[b], j[b] ); int cur = 0; int ans = 0; while( cur < n*m ){ Node aux = query( 1, 0, n*m - 1, 0, cur ); if( aux.area() == cur + 1 ){ ans++; cur++; } else{ cur = aux.area() - 1; } } return ans; } for( int k = min(a, b) + 1; k <= max(a, b) + 1; k++ ){ if( marc[k] ){ marc[k] = 0; resp--; } linha1[k] = min(linha1[k - 1], i[k - 1] ); linha2[k] = max(linha2[k - 1], i[k - 1] ); coluna1[k] = min(coluna1[k - 1], j[k - 1] ); coluna2[k] = max(coluna2[k - 1], j[k - 1] ); if( (linha2[k] - linha1[k] + 1)*(coluna2[k] - coluna1[k] + 1) == k ){ marc[k] = 1; resp++; } } return resp; }
#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...