제출 #294455

#제출 시각아이디문제언어결과실행 시간메모리
294455amiratou자리 배치 (IOI18_seats)C++14
17 / 100
4054 ms43640 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define sz(x) (int)(x.size()) const int MX = (int)(1e6+3); const int INF = (int)(1e9); typedef pair<int,int> ii; int ans[MX],fen[MX]; vector<int> r,c; ii range[MX][2]; void update(int idx,int val){ for (int i = idx; i <= sz(r); i+=(i&(-i))) fen[i]+=val; } int get(int idx){ int h=0; for (int i = idx; i >= 1; i-=(i&(-i))) h+=fen[i]; return h; } void add(int a,int b,int val){ update(a,val); if(b!=sz(r))update(b+1,-val); } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { r=R,c=C; for (int i = 0; i < H*W; ++i) { range[i][0]=range[i][1]={INF,-1}; if(i){ range[i][0].fi=min(range[i][0].fi,range[i-1][0].fi); range[i][0].se=max(range[i][0].se,range[i-1][0].se); range[i][1].fi=min(range[i][1].fi,range[i-1][1].fi); range[i][1].se=max(range[i][1].se,range[i-1][1].se); int k=get(i); add(i+1,i+1,k); } range[i][0].fi=min(range[i][0].fi,R[i]); range[i][0].se=max(range[i][0].se,R[i]); range[i][1].fi=min(range[i][1].fi,C[i]); range[i][1].se=max(range[i][1].se,C[i]); if(((range[i][0].se-range[i][0].fi+1)*(range[i][1].se-range[i][1].fi+1))==(i+1))add(i+1,i+1,1); } } int swap_seats(int a, int b) { if(a>b)swap(a,b); swap(r[a],r[b]),swap(c[a],c[b]); if(b!=sz(r)){ int k=get(b+1); add(b+2,sz(r),-k); } for (int i = a; i <= b; ++i) { range[i][0]=range[i][1]={INF,-1}; int k=get(i+1); add(i+1,i+1,-k); if(i){ range[i][0].fi=min(range[i][0].fi,range[i-1][0].fi); range[i][0].se=max(range[i][0].se,range[i-1][0].se); range[i][1].fi=min(range[i][1].fi,range[i-1][1].fi); range[i][1].se=max(range[i][1].se,range[i-1][1].se); int k=get(i); add(i+1,i+1,k); } range[i][0].fi=min(range[i][0].fi,r[i]); range[i][0].se=max(range[i][0].se,r[i]); range[i][1].fi=min(range[i][1].fi,c[i]); range[i][1].se=max(range[i][1].se,c[i]); if(((range[i][0].se-range[i][0].fi+1)*(range[i][1].se-range[i][1].fi+1))==(i+1))add(i+1,i+1,1); } if(b!=sz(r)){ int k=get(b+1); add(b+2,sz(r),k); } return get(sz(r)); }
#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...