Submission #991368

#TimeUsernameProblemLanguageResultExecution timeMemory
991368PCTprobabilitySeats (IOI18_seats)C++17
17 / 100
4038 ms55740 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; int r[1010101],c[1010101]; int mr[1010101][2],mc[1010101][2]; int n,m; int ans=0; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { n=H,m=W; for(int i=0;i<n*m;i++){ r[i]=R[i]; c[i]=C[i]; mr[i][0]=mr[i][1]=R[i]; mc[i][0]=mc[i][1]=C[i]; } for(int i=1;i<n*m;i++){ mr[i][0]=min(mr[i][0],mr[i-1][0]); mr[i][1]=max(mr[i][1],mr[i-1][1]); mc[i][0]=min(mc[i][0],mc[i-1][0]); mc[i][1]=max(mc[i][1],mc[i-1][1]); } for(int i=0;i<n*m;i++){ //cout<<i<<" "<<r[i]<<" "<<c[i]<<" "<<mr[i][1]<<" "<<mr[i][0]<<" "<<mc[i][1]<<" "<<mc[i][0]<<" "<<(mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)<<endl; if((mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)==i+1) ans++; } } int swap_seats(int a, int b) { if(a>b) swap(a,b); swap(r[a],r[b]); swap(c[a],c[b]); //cout<<a<<" "<<b<<endl; for(int i=a;i<b;i++){ //cout<<i<<" "<<r[i]<<" "<<c[i]<<" "<<mr[i][1]<<" "<<mr[i][0]<<" "<<mc[i][1]<<" "<<mc[i][0]<<" "<<(mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)<<endl; if((mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)==i+1) ans--; if(i){ mr[i][0]=min(r[i],mr[i-1][0]); mr[i][1]=max(r[i],mr[i-1][1]); mc[i][0]=min(c[i],mc[i-1][0]); mc[i][1]=max(c[i],mc[i-1][1]); } else{ mr[i][0]=mr[i][1]=r[i]; mc[i][0]=mc[i][1]=c[i]; } //cout<<i<<" "<<r[i]<<" "<<c[i]<<" "<<mr[i][1]<<" "<<mr[i][0]<<" "<<mc[i][1]<<" "<<mc[i][0]<<" "<<(mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)<<endl; if((mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)==i+1) ans++; } return ans; }
#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...