oj.uz

답안 #349725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349725 2021-01-18T09:32:00 Z Bill_00 The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 1313 ms 262148 KB 
#include <bits/stdc++.h>
#define N 200000
#define M 100000
#define pb push_back
using namespace std;
int h[M],pre[N];
unordered_map<int,vector<int> >v[M];
vector<int>day[N];
void init(int n,int d, int H[]){
	for(int i=0;i<n;i++) h[i]=H[i];
}

void curseChanges(int u, int A[], int B[]){
	for(int i=1;i<=u;i++){
		int a=A[i-1],b=B[i-1];
		day[a].pb(i);
		day[b].pb(i);
		if(pre[a]==0){
			v[a][i].pb(b);
			pre[a]=i;
		}
		else{
			bool flag=0;
			for(int j:v[a][pre[a]]){
				if(j==b){
					flag=1;
					continue;
				}
				v[a][i].pb(j);
			}
			if(flag==0) v[a][i].pb(b);
			pre[a]=i;
		}
		if(pre[b]==0){
			v[b][i].pb(a);
			pre[b]=i;
		}
		else{
			bool flag=0;
			for(int j:v[b][pre[b]]){
				if(j==a){
					flag=1;
					continue;
				}
				v[b][i].pb(j);
			}
			if(flag==0) v[b][i].pb(a);
			pre[b]=i;
		}
	}
}

int question(int x, int y, int z) {
	int ans=1e9;
	int id=upper_bound(day[x].begin(),day[x].end(),z)-day[x].begin();
	--id;
	int e=day[x].size()-1;
	if(id<0 || id>e){
		return ans;
	}
	int a=day[x][id];
	id=upper_bound(day[y].begin(),day[y].end(),z)-day[y].begin();
	--id;
	e=day[y].size()-1;
	if(id<0 || id>e){
		return ans;
	}
	int b=day[y][id];
	// cout << a << ' ' << b << '\n';
	if(v[x][a].size()==0 || v[y][b].size()==0){
		return ans;
	}
	vector<int>xx,yy;
	for(int V:v[y][b]){
		yy.pb(h[V]);
	}
	sort(yy.begin(),yy.end());
	for(int U:v[x][a]){
		int id=lower_bound(yy.begin(),yy.end(),h[U])-yy.begin();
		ans=min(ans,abs(h[U]-yy[max(0,id-1)]));
		int r=yy.size()-1;
		ans=min(ans,abs(yy[min(id,r)]-h[U]));
	}
	return ans;
}

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10476 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10732 KB Output is correct
2 Correct 9 ms 10732 KB Output is correct
3 Correct 9 ms 10732 KB Output is correct
4 Correct 24 ms 12012 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 561 ms 55084 KB Output is correct
2 Correct 562 ms 54892 KB Output is correct
3 Correct 661 ms 66688 KB Output is correct
4 Runtime error 1194 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 55020 KB Output is correct
2 Runtime error 1313 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 12908 KB Output is correct
2 Correct 104 ms 13292 KB Output is correct
3 Correct 127 ms 13324 KB Output is correct
4 Correct 689 ms 19948 KB Output is correct
5 Correct 620 ms 18540 KB Output is correct
6 Correct 108 ms 13420 KB Output is correct
7 Correct 542 ms 18540 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10476 KB Output is correct
2 Correct 10 ms 10732 KB Output is correct
3 Correct 9 ms 10732 KB Output is correct
4 Correct 9 ms 10732 KB Output is correct
5 Correct 24 ms 12012 KB Output is correct
6 Correct 561 ms 55084 KB Output is correct
7 Correct 562 ms 54892 KB Output is correct
8 Correct 661 ms 66688 KB Output is correct
9 Runtime error 1194 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -