제출 #81168

#제출 시각아이디문제언어결과실행 시간메모리
81168cki86201자리 배치 (IOI18_seats)C++11
26 / 100
2733 ms118420 KiB
#include "seats.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <iostream> #include <functional> #include <unordered_set> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define Fi first #define Se second #define pb(x) push_back(x) #define szz(x) (int)x.size() #define rep(i,n) for(int i=0;i<n;i++) #define all(x) x.begin(),x.end() typedef tuple<int, int, int> t3; int R[1000010], C[1000010]; int valR[1000010][2], valC[1000010][2]; int N, M, P; int ans; int subtask_3; namespace S3 { set <int> sx[1010], sy[1010]; int solve(int N, int M) { vector <pii> A(N+1), B(M+1); for(int i=1;i<=N+1;i++) A[i-1] = pii(*sx[i].begin(), i); for(int i=1;i<=M+1;i++) B[i-1] = pii(*sy[i].begin(), i); sort(all(A)); sort(all(B)); int valr[2] = {A[0].Se, A[0].Se}; int valc[2] = {B[0].Se, B[0].Se}; int res = 0; for(int i=1, j=1;i<=N;i++) { while(j <= M && B[j].Fi < A[i].Fi) { if(A[i-1].Fi != B[j].Fi && (valr[1]-valr[0]+1) * (valc[1]-valc[0]+1) == B[j].Fi-1) ++res; valc[1] = max(valc[1], B[j].Se); valc[0] = min(valc[0], B[j].Se); ++j; } if((valr[1]-valr[0]+1) * (valc[1]-valc[0]+1) == A[i].Fi-1) ++res; valr[1] = max(valr[1], A[i].Se); valr[0] = min(valr[0], A[i].Se); } return res; } } int check_on_naive(int x) { return (valR[x][1] - valR[x][0] + 1) * (valC[x][1] - valC[x][0] + 1) == x; } void give_initial_chart(int H, int W, std::vector<int> tR, std::vector<int> tC) { N = H; M = W; P = N * M; rep(i, P) R[i + 1] = tR[i] + 1, C[i + 1] = tC[i] + 1; if(H <= 1000 && W <= 1000) { subtask_3 = 1; for(int i=1;i<=P;i++) { S3::sx[R[i]].insert(i); S3::sy[C[i]].insert(i); } S3::sx[H+1].insert(P+1); S3::sy[W+1].insert(P+1); return; } valR[0][0] = 1e9, valR[0][1] = -1; valC[0][0] = 1e9, valC[0][1] = -1; for(int i=1;i<=P;i++) { valR[i][0] = min(valR[i-1][0], R[i]); valR[i][1] = max(valR[i-1][1], R[i]); valC[i][0] = min(valC[i-1][0], C[i]); valC[i][1] = max(valC[i-1][1], C[i]); } for(int i=1;i<=P;i++) { ans += check_on_naive(i); } } int swap_seats(int a, int b) { ++a; ++b; if(a > b) swap(a, b); if(subtask_3) { int ra = R[a], rb = R[b]; S3::sx[ra].erase(a); S3::sx[ra].insert(b); S3::sx[rb].erase(b); S3::sx[rb].insert(a); int ca = C[a], cb = C[b]; S3::sy[ca].erase(a); S3::sy[ca].insert(b); S3::sy[cb].erase(b); S3::sy[cb].insert(a); swap(R[a], R[b]); swap(C[a], C[b]); return S3::solve(N, M); } if(b-a <= 10000) { swap(R[a], R[b]); swap(C[a], C[b]); for(int i=a;i<b;i++) ans -= check_on_naive(i); for(int i=a;i<b;i++) { valR[i][0] = min(valR[i-1][0], R[i]); valR[i][1] = max(valR[i-1][1], R[i]); valC[i][0] = min(valC[i-1][0], C[i]); valC[i][1] = max(valC[i-1][1], C[i]); ans += check_on_naive(i); } return ans; } return 0; }
#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...