Submission #644557

#	Time	Username	Problem	Language	Result	Execution time	Memory
644557		Markomafko972	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	754 ms	58688 KiB

Main

#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[400005];
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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25