oj.uz

Submission #80248

# Submission time Handle Problem Language Result Execution time Memory
80248 2018-10-19T16:41:35 Z KLPP Seats (IOI18_seats) C++14
0 / 100
 561 ms 45220 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]);
	}
	/*for(int i=1;i<8;i++){
		cout<<counter[i]<<" "<<i<<endl;
	}*/
	//for(int i=0;i<w;i++)cout<<arr[i]<<endl;
	return counter[1];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 19532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 19532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19532 KB Output is correct
2 Correct 45 ms 19532 KB Output is correct
3 Correct 63 ms 19532 KB Output is correct
4 Correct 89 ms 19532 KB Output is correct
5 Correct 113 ms 19532 KB Output is correct
6 Incorrect 561 ms 45220 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -