oj.uz

Submission #1042050

# Submission time Handle Problem Language Result Execution time Memory
1042050 2024-08-02T13:21:40 Z ALeonidou Wall (IOI14_wall) C++17
24 / 100
 142 ms 30536 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define ll int
#define F first
#define S second
#define sz(x) (ll)x.size()
#define endl "\n"
#define pb push_back
#define inf 1000000000

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
typedef pair <ll, ii> iii;
typedef vector <iii> viii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void buildWall(ll n, ll k, ll op[], ll left[], ll right[], ll height[], ll finalHeight[]){

	// for (ll i =0; i<k; i++){
	// 	left[i]--;
	// 	right[i]--;
	// }

	vector <vii> q(n, vii());
	ll lastI = -1;
	for (ll i =0; i<k && op[i] == 1; i++){
		q[left[i]].pb(ii(height[i], right[i]));
		lastI = i;
	}

	priority_queue <ii, vii, less<ii> > pq1;
	ll curH = 0, curR = 0;
	for (ll i = 0; i<n; i++){
		// dbg3(i, curH, curR);
		if (i > curR){
			// dbg2(i,curR)
			curH = 0;
		}
		for (ll j =0; j<sz(q[i]); j++){
			pq1.push(q[i][j]);
		}
		
		while (!pq1.empty() && pq1.top().S < i) pq1.pop();
		if (!pq1.empty()){
			ii f = pq1.top();
			ll h = f.F;
			ll r = f.S;

			if (h > curH){
				// cout<<"IN"<<endl;
				pq1.pop();
				if (curH > 0){
					pq1.push(ii(curH, curR));
				}
				curH = h;
				curR = r;
			}
		}
		// dbg(curH);

		finalHeight[i] = curH;
		// cout<<endl;
	}

	// return;

	q.assign(n, vii());
	for (ll i =lastI+1; i<k; i++){
		q[left[i]].pb(ii(height[i], right[i]));
	}
	// for (ll i =0; i<n; i++){
	// 	for (ll j =0; j<sz(q[i]); j++){
	// 		cout<<"("<<q[i][j].F<<" "<<q[i][j].S<<") ";
	// 	}
	// 	cout<<endl;
	// }
	priority_queue <ii, vii, greater<ii> > pq2;
	curH = inf, curR = 0;
	for (ll i = 0; i<n; i++){
		// dbg3(i,curH, curR);
		if (i > curR){
			curH = inf;
		}
		for (ll j =0; j<sz(q[i]); j++){
			pq2.push(q[i][j]);
		}
		
		while (!pq2.empty() && pq2.top().S < i) pq2.pop();
		if (!pq2.empty()){
			ii f = pq2.top();
			ll h = f.F;
			ll r = f.S;
			
			if (h < curH){
				pq2.pop();
				if (curH < inf){
					pq2.push(ii(curH, curR));
				}
				curH = h;
				curR = r;
			}
		}

		finalHeight[i] = min(finalHeight[i], curH);
	}

	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 86 ms 22616 KB Output is correct
3 Correct 50 ms 11972 KB Output is correct
4 Correct 142 ms 30536 KB Output is correct
5 Correct 137 ms 30496 KB Output is correct
6 Correct 124 ms 24260 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -