oj.uz

Submission #589135

# Submission time Handle Problem Language Result Execution time Memory
589135 2022-07-04T09:38:17 Z Arnch The Potion of Great Power (CEOI20_potion) C++17
18 / 100
 423 ms 215960 KB 
#include<bits/stdc++.h>
using namespace std;

#define mak make_pair
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

const int N = 1e3 + 10, maxn = 1e6 + 10;

int n, d, h[maxn], a[maxn], b[maxn];
map<pair<int, int>, int> mp;
vector<pair<int, int> > vc[maxn][2];
vector<int> mn[maxn][2];

void init(int N, int D, int H[]) {
	n = N, d = D;
	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++) {
		a[i] = A[i - 1], b[i] = B[i - 1];
		if(a[i] > b[i]) swap(a[i], b[i]);
	}

	for(int i = 1; i <= U; i++) {
		if(mp[mak(a[i], b[i])] == 0) {
			mp[mak(a[i], b[i])] = i;
		} else {
			vc[a[i]][h[b[i]]].push_back({i - 1, mp[mak(a[i], b[i])]});
			vc[b[i]][h[a[i]]].push_back({i - 1, mp[mak(a[i], b[i])]});
			mp.erase(mak(a[i], b[i]));
		}
	}

	for(auto i : mp) {
		vc[i.first.first][h[i.first.second]].push_back({U, i.second});
		vc[i.first.second][h[i.first.first]].push_back({U, i.second});
	}
	mp.clear();

	for(int i = 0; i < n; i++) sort(All(vc[i][0])), sort(All(vc[i][1]));
	for(int i = 0; i < n; i++) {
		int cnt = 1e9;
		for(int j = 0; j < Sz(vc[i][0]); j++) mn[i][0].push_back(cnt);
		for(int j = Sz(vc[i][0]) - 1; j >= 0; j--) {
			cnt = min(cnt, vc[i][0][j].second);
			mn[i][0][j] = cnt;
		}
		
		cnt = 1e9;
		for(int j = 0; j < Sz(vc[i][1]); j++) mn[i][1].push_back(cnt);
		for(int j = Sz(vc[i][1]) - 1; j >= 0; j--) {
			cnt = min(cnt, vc[i][1][j].second);
			mn[i][1][j] = cnt;
		}
	}
}

int question(int x, int y, int v) {
	int ans = 1e9;

	pair<bool, bool> p1, p2;
	p1 = mak(0, 0), p2 = p1;

	int ind = lower_bound(All(vc[x][0]), mak(v, 0)) - vc[x][0].begin();
	if(ind < Sz(vc[x][0]) && mn[x][0][ind] <= v) {
		p1.first = 1;		
	}
	
	ind = lower_bound(All(vc[x][1]), mak(v, 0)) - vc[x][1].begin();
	if(ind < Sz(vc[x][1]) && mn[x][1][ind] <= v) {
		p1.second = 1;	
	}

	ind = lower_bound(All(vc[y][0]), mak(v, 0)) - vc[y][0].begin();
	if(ind < Sz(vc[y][0]) && mn[y][0][ind] <= v) {
		p2.first = 1;		
	}
	
	ind = lower_bound(All(vc[y][1]), mak(v, 0)) - vc[y][1].begin();
	if(ind < Sz(vc[y][1]) && mn[y][1][ind] <= v) {
		p2.second = 1;		
	}

	if(p1.first == p2.first && p1.first == 1) return 0;
	if(p1.second == p2.second && p1.second == 1) return 0;

	if(p1.first == p2.second && p1.first == 1) return 1;
	if(p1.second == p2.first && p1.second == 1) return 1;

	return ans;
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 94152 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 191068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 279 ms 215960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 117600 KB Output is correct
2 Correct 239 ms 103112 KB Output is correct
3 Correct 316 ms 106928 KB Output is correct
4 Correct 347 ms 107112 KB Output is correct
5 Correct 423 ms 117084 KB Output is correct
6 Correct 359 ms 106996 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 192412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 94152 KB Incorrect
2 Halted 0 ms 0 KB -