제출 #1042923

#제출 시각아이디문제언어결과실행 시간메모리
1042923Itamar자리 배치 (IOI18_seats)C++14
0 / 100
135 ms32568 KiB
#include<bits/stdc++.h> using namespace std; const int siz = 1e3+2; int p[siz]; int v[siz]; int N; struct node{ int l,r,mid,maxi,cam,pl; // num of elements equal to maxi node* sl = NULL,*sr; node(int li, int ri){ l = li, r = ri, mid = (l+r)/2, maxi = 0,cam=0,pl=0; if(l<r){ sl = new node(l,mid); sr = new node(mid+1,r); }else if(l > 0 && l <= N)cam = 1; } void push(){ if(sl == NULL)return; sl->maxi+=pl; sr->maxi+=pl; sr->pl+=pl; sl->pl+=pl; pl=0; } void update(int a, int b, int val){ if(a > r || b < l)return; push(); if(a <= l && b>=r){ maxi+=val; pl += val; }else{ sl->update(a,b,val); sr->update(a,b,val); if(sl->maxi > sr->maxi)cam = sl->cam; else if(sl->maxi < sr->maxi)cam = sr->cam; else cam = sl->cam+sr->cam; maxi = max(sl->maxi,sr->maxi); } } }; node* seg; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { N=W; p[0]=N+1; p[N+1]=N+1; seg = new node(1,N); for(int i = 0; i <W; i++)p[C[i]+1]=i+1; for(int i = 0; i < N; i++)v[i+1] = C[i]+1; for(int i = 1; i < N; i++){ seg->update(max(p[i],p[i+1]),N,1); } for(int i = 1; i <= N; i++)seg->update(i,N,-1); } int swap_seats(int a, int b) { a++,b++; seg->update(max(p[v[a]],p[v[a]+1]),1e6,-1); seg->update(max(p[v[a]],p[v[a]-1]),1e6,-1); seg->update(max(p[v[b]],p[v[b]+1]),1e6,-1); seg->update(max(p[v[b]],p[v[b]-1]),1e6,-1); swap(p[v[a]],p[v[b]]); seg->update(max(p[v[a]],p[v[a]+1]),1e6,1); seg->update(max(p[v[a]],p[v[a]-1]),1e6,1); seg->update(max(p[v[b]],p[v[b]+1]),1e6,1); seg->update(max(p[v[b]],p[v[b]-1]),1e6,1); swap(v[a],v[b]); return seg->cam; }
#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...