oj.uz

Submission #644556

# Submission time Handle Problem Language Result Execution time Memory
644556 2022-09-25T00:50:20 Z Markomafko972 Abracadabra (CEOI22_abracadabra) C++14
35 / 100
 466 ms 119000 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, q, koji = 0, vri, w;
int a[200005];
int veci[200005];
int gdje[200005];
stack< pair<int, int> > st;
set< pair< pair<int, int>, pair<int, int> > > s;
set< pair< pair<int, int>, pair<int, int> > > :: iterator it;
vector< pair< pair<int, int>, pair<int, int> > > v;
vector< pair<int, int> > kad[200005];
int sol[1000005];

int t[2*OFF+5];

void update(int x, int y) {
	x += OFF;
	t[x] = y;
	x /= 2;
	while (x > 0) {
		t[x] = t[x*2] + t[x*2+1];
		x /= 2;
	}
}

void ispis() {
	int pot = 2;
	for (int i = 1; i < 2*OFF; i++) {
		if (i == pot) {
			cout << endl;
			pot *= 2;
		}
		
		cout << t[i] << " ";
	}
	cout << endl;
}

int query(int x, int y) {
	if (x >= OFF) {
		int prva = v[x-OFF].Y.X;
		return a[prva+y-1];
	}
	
	if (t[x*2] >= y) return query(x*2, y);
	else return query(x*2+1, y-t[x*2]); 
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		veci[i] = n;
	}
	
	for (int i = n-1; i >= 0; i--) {
		while (st.size() > 0 && st.top().X <= a[i]) {
			st.pop();
		}
		
		if (st.size() > 0) veci[i] = st.top().Y;
		st.push({a[i], i});
	}
	
	int pos = 0;
	while (pos < n) {
		s.insert({{a[pos], koji}, {pos, veci[pos]-1}});
		v.push_back({{a[pos], koji}, {pos, veci[pos]-1}});
		koji++;
		pos = veci[pos];
	}
	
	int d = n;
	for (int i = 0; i < n; i++) {
		while (1) {
			it = s.end();
			it--;
			
			if (d+(*it).Y.X-(*it).Y.Y-1 < n/2) break;
			else {
				d = d+(*it).Y.X-(*it).Y.Y-1;
				s.erase(it);
			}
		}
		
		//cout << i << ": " << d << endl;
		if (d > n/2) {
			it = s.end();
			it--;			
			pos = (*it).Y.X;
			int kr = (*it).Y.Y;
			d -= (kr-pos+1);
			s.erase(it);
			
			int dod = n/2 - d;
			
			s.insert({{a[pos], koji}, {pos, pos+dod-1}});
			v.push_back({{a[pos], koji}, {pos, pos+dod-1}});
			d += dod;
			//cout << "novi: " << pos << " " << pos+dod-1 << endl;
			koji++;
			pos += dod;
			
			while (pos <= kr) {
				s.insert({{a[pos], koji}, {pos, min(veci[pos]-1, kr)}});
				v.push_back({{a[pos], koji}, {pos, min(veci[pos]-1, kr)}});
				d += min(veci[pos]-1, kr) - pos + 1;
				//cout << "novi: " << pos << " " << min(veci[pos]-1, kr) << endl;
				koji++;
				pos = veci[pos];
			}
		}
	}
	
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		gdje[v[i].X.Y] = i;
		//cout << v[i].Y.X << " " << v[i].Y.Y << " | " << v[i].X.X << endl;
	}
	
	// gotov precompute
	s.clear();
	
	pos = 0;
	koji = 0;
	while (pos < n) {
		s.insert({{a[pos], koji}, {pos, veci[pos]-1}});
		update(gdje[koji], veci[pos]-pos);
		//ispis();
		koji++;
		pos = veci[pos];
	}
	
	for (int i = 0; i < q; i++) {
		cin >> vri >> w;
		kad[min(n, vri)].push_back({w, i});
	}
	
	d = n;
	for (int i = 0; i <= n; i++) {
		
		//ispis();
		for (int j = 0; j < (int)kad[i].size(); j++) {
			int trenrj = query(1, kad[i][j].X);
			sol[kad[i][j].Y] = trenrj;
		}
		
		if (i == n) break;
		
		while (1) {
			it = s.end();
			it--;
			
			if (d+(*it).Y.X-(*it).Y.Y-1 < n/2) break;
			else {
				d = d+(*it).Y.X-(*it).Y.Y-1;
				//update(gdje[(*it).X.Y], 0);
				s.erase(it);
			}
		}
		
		if (d > n/2) {
			it = s.end();
			it--;			
			pos = (*it).Y.X;
			int kr = (*it).Y.Y;
			d -= (kr-pos+1);
			update(gdje[(*it).X.Y], 0);
			s.erase(it);
			
			int dod = n/2 - d;
			
			s.insert({{a[pos], koji}, {pos, pos+dod-1}});
			update(gdje[koji], dod);
			d += dod;
			koji++;
			pos += dod;
			
			while (pos <= kr) {
				s.insert({{a[pos], koji}, {pos, min(veci[pos]-1, kr)}});
				update(gdje[koji], min(veci[pos]-1, kr)-pos+1);
				d += min(veci[pos]-1, kr) - pos + 1;
				koji++;
				pos = veci[pos];
			}
		}
	}
	
	
	for (int i = 0; i < q; i++) cout << sol[i] << "\n";

	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 24264 KB Output is correct
2 Correct 269 ms 25824 KB Output is correct
3 Correct 250 ms 25056 KB Output is correct
4 Correct 204 ms 27432 KB Output is correct
5 Correct 228 ms 29260 KB Output is correct
6 Correct 209 ms 29656 KB Output is correct
7 Correct 239 ms 29368 KB Output is correct
8 Correct 218 ms 27516 KB Output is correct
9 Correct 213 ms 26984 KB Output is correct
10 Correct 220 ms 26020 KB Output is correct
11 Correct 218 ms 26248 KB Output is correct
12 Correct 212 ms 24564 KB Output is correct
13 Correct 215 ms 25340 KB Output is correct
14 Correct 231 ms 29608 KB Output is correct
15 Correct 225 ms 27508 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 234 ms 25692 KB Output is correct
18 Correct 195 ms 25576 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 19212 KB Output is correct
2 Correct 122 ms 18468 KB Output is correct
3 Correct 130 ms 17328 KB Output is correct
4 Correct 53 ms 10564 KB Output is correct
5 Correct 99 ms 14728 KB Output is correct
6 Correct 58 ms 11204 KB Output is correct
7 Correct 85 ms 12776 KB Output is correct
8 Correct 67 ms 11944 KB Output is correct
9 Correct 85 ms 13752 KB Output is correct
10 Correct 42 ms 9532 KB Output is correct
11 Correct 43 ms 9408 KB Output is correct
12 Correct 43 ms 9484 KB Output is correct
13 Correct 44 ms 9556 KB Output is correct
14 Correct 51 ms 9740 KB Output is correct
15 Correct 37 ms 8972 KB Output is correct
16 Correct 14 ms 6432 KB Output is correct
17 Correct 84 ms 18800 KB Output is correct
18 Correct 33 ms 8688 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 2 ms 5036 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 24264 KB Output is correct
2 Correct 269 ms 25824 KB Output is correct
3 Correct 250 ms 25056 KB Output is correct
4 Correct 204 ms 27432 KB Output is correct
5 Correct 228 ms 29260 KB Output is correct
6 Correct 209 ms 29656 KB Output is correct
7 Correct 239 ms 29368 KB Output is correct
8 Correct 218 ms 27516 KB Output is correct
9 Correct 213 ms 26984 KB Output is correct
10 Correct 220 ms 26020 KB Output is correct
11 Correct 218 ms 26248 KB Output is correct
12 Correct 212 ms 24564 KB Output is correct
13 Correct 215 ms 25340 KB Output is correct
14 Correct 231 ms 29608 KB Output is correct
15 Correct 225 ms 27508 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 234 ms 25692 KB Output is correct
18 Correct 195 ms 25576 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Runtime error 466 ms 119000 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -