# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
80250 |
2018-10-19T16:45:00 Z |
KLPP |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
41768 KB |
#include "seats.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long int lld;
int h,w;
int per[1000000];
int inv[1000000];
int arr[1000000];
//segtree
int sum[1000000];
int minimo[1000000];
int counter[1000000];
void update_pos(int i){
int pos=inv[i];
arr[i]=-1;
if(pos==0 || per[pos-1]>i){
arr[i]++;
}
if(pos==w-1 || per[pos+1]>i){
arr[i]++;
}
}
void build(int a, int b, int node){
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
sum[node]=sum[2*node]+sum[2*node+1];
minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==minimo[2*node+1]+sum[2*node]){
counter[node]+=counter[2*node+1];
}
}
void update(int a, int b, int node, int pos){
if(pos<a || b<pos)return;
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,pos);
update(mid+1,b,2*node+1,pos);
sum[node]=sum[2*node]+sum[2*node+1];
minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==minimo[2*node+1]+sum[2*node]){
counter[node]+=counter[2*node+1];
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;
w=W;
for(int i=0;i<w;i++){
inv[i]=C[i];
per[C[i]]=i;
}
for(int i=0;i<w;i++){
int pos=inv[i];
arr[i]=-1;
if(pos==0 || per[pos-1]>i){
arr[i]++;
}
if(pos==w-1 || per[pos+1]>i){
arr[i]++;
}
//cout<<arr[i]<<endl;
}
build(0,w-1,1);
//cout<<counter[1]<<endl;
/*for(int i=1;i<8;i++){
cout<<counter[i]<<" "<<i<<endl;
}*/
}
int swap_seats(int a, int b) {
int pos_a=inv[a];
int pos_b=inv[b];
swap(inv[a],inv[b]);
swap(per[pos_a],per[pos_b]);
update_pos(a);
update(0,w-1,1,a);
update_pos(b);
update(0,w-1,1,b);
if(inv[a]>0){
update_pos(per[inv[a]-1]);
update(0,w-1,1,per[inv[a]-1]);
}
if(inv[a]<w-1){
update_pos(per[inv[a]+1]);
update(0,w-1,1,per[inv[a]+1]);
}
if(inv[b]>0){
update_pos(per[inv[b]-1]);
update(0,w-1,1,per[inv[b]-1]);
}
if(inv[b]<w-1){
update_pos(per[inv[b]+1]);
update(0,w-1,1,per[inv[b]+1]);
}
int ans=0;
int sum=0;
for(int i=0;i<w;i++){
sum+=arr[i];
if(sum==1)ans++;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
347 ms |
17212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
17212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
17212 KB |
Output is correct |
2 |
Correct |
59 ms |
17212 KB |
Output is correct |
3 |
Correct |
70 ms |
17212 KB |
Output is correct |
4 |
Correct |
145 ms |
17212 KB |
Output is correct |
5 |
Correct |
632 ms |
17212 KB |
Output is correct |
6 |
Execution timed out |
4032 ms |
41768 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |