oj.uz

Submission #920518

# Submission time Handle Problem Language Result Execution time Memory
920518 2024-02-02T17:03:59 Z Nika533 Wall (IOI14_wall) C++17
100 / 100
 581 ms 163352 KB 
#pragma GCC diagnostic warning "-std=c++11"

#include <bits/stdc++.h>
#include "wall.h"

#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>

using namespace std;

const int N=2e6+5,K=5e5+5;

pii t[K*4];
vector<int> L[N],R[N];

pii merge(pii a, pii b) {
	pii c;
	if (b.f==-1) return b;
	if (a.f==-1) {
		c.f=-1;
		if (a.s<b.f) c.s=b.f;
		else if (a.s>b.s) c.s=b.s;
		else c.s=a.s;
		return c;
	}
	int l=max(a.f,b.f),r=min(a.s,b.s);
	if (l<=r) return {l,r};
	if (a.s<b.s) return {-1,b.f};
	else return {-1,b.s};
}

void update(int v, int tl, int tr, int ind, int x, int y) {
	if (tl==tr) {
		t[v]={x,y};
		return;
	}
	int mid=(tl+tr)/2;
	if (ind<=mid) update(v*2,tl,mid,ind,x,y);
	else update(v*2+1,mid+1,tr,ind,x,y);
	t[v]=merge(t[v*2],t[v*2+1]);
}

pii query(int v, int tl, int tr, int l, int r) {
	if (tl==l && tr==r) return t[v];
	int mid=(tl+tr)/2;
	if (r<=mid) return query(v*2,tl,mid,l,r);
	else if (mid+1<=l) return query(v*2+1,mid+1,tr,l,r);
	else return merge(query(v*2,tl,mid,l,mid),query(v*2+1,mid+1,tr,mid+1,r));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	for (int i=0; i<k; i++) {
		L[left[i]].pb(i);
		R[right[i]].pb(i);
	}
	
	for (int i=0; i<k; i++) update(1,0,k-1,i,0,1e9);
	
	for (int i=0; i<n; i++) {
		
//		cout<<"I "<<i<<endl;
//		
//		for (int i=0; i<k*4; i++) {
//			cout<<"TTT "<<i<<" "<<t[i].f<<" "<<t[i].s<<endl;
//		}
		
		if (i) {
			for (auto x:R[i-1]) {
				update(1,0,k-1,x,0,1e9);
			}
		}
		
		for (auto x:L[i]) {
			if (op[x]==1) update(1,0,k-1,x,height[x],1e9);
			else update(1,0,k-1,x,0,height[x]);
		}
		
		pii ans=query(1,0,k-1,0,k-1);
		
		if (ans.f==-1) finalHeight[i]=ans.s;
		else finalHeight[i]=ans.f;
	}
}

Compilation message

wall.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 94808 KB Output is correct
2 Correct 27 ms 95068 KB Output is correct
3 Correct 27 ms 95112 KB Output is correct
4 Correct 31 ms 95320 KB Output is correct
5 Correct 31 ms 95324 KB Output is correct
6 Correct 29 ms 95320 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 94808 KB Output is correct
2 Correct 254 ms 120756 KB Output is correct
3 Correct 206 ms 109540 KB Output is correct
4 Correct 509 ms 130632 KB Output is correct
5 Correct 365 ms 129400 KB Output is correct
6 Correct 351 ms 127540 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 95068 KB Output is correct
2 Correct 28 ms 95148 KB Output is correct
3 Correct 26 ms 95068 KB Output is correct
4 Correct 30 ms 95320 KB Output is correct
5 Correct 30 ms 95312 KB Output is correct
6 Correct 31 ms 95324 KB Output is correct
7 Correct 26 ms 94808 KB Output is correct
8 Correct 259 ms 120760 KB Output is correct
9 Correct 182 ms 109392 KB Output is correct
10 Correct 549 ms 130780 KB Output is correct
11 Correct 354 ms 129436 KB Output is correct
12 Correct 355 ms 127704 KB Output is correct
13 Correct 26 ms 94808 KB Output is correct
14 Correct 256 ms 120796 KB Output is correct
15 Correct 52 ms 96848 KB Output is correct
16 Correct 551 ms 130904 KB Output is correct
17 Correct 364 ms 127868 KB Output is correct
18 Correct 366 ms 127464 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 94808 KB Output is correct
2 Correct 28 ms 95068 KB Output is correct
3 Correct 27 ms 95068 KB Output is correct
4 Correct 30 ms 95528 KB Output is correct
5 Correct 31 ms 95320 KB Output is correct
6 Correct 33 ms 95316 KB Output is correct
7 Correct 26 ms 94812 KB Output is correct
8 Correct 262 ms 121208 KB Output is correct
9 Correct 188 ms 109516 KB Output is correct
10 Correct 581 ms 130820 KB Output is correct
11 Correct 363 ms 129500 KB Output is correct
12 Correct 353 ms 127540 KB Output is correct
13 Correct 25 ms 94808 KB Output is correct
14 Correct 260 ms 121220 KB Output is correct
15 Correct 51 ms 96864 KB Output is correct
16 Correct 521 ms 130884 KB Output is correct
17 Correct 376 ms 127864 KB Output is correct
18 Correct 367 ms 127460 KB Output is correct
19 Correct 524 ms 162980 KB Output is correct
20 Correct 510 ms 160516 KB Output is correct
21 Correct 554 ms 162964 KB Output is correct
22 Correct 515 ms 160848 KB Output is correct
23 Correct 523 ms 160600 KB Output is correct
24 Correct 517 ms 160520 KB Output is correct
25 Correct 521 ms 160516 KB Output is correct
26 Correct 520 ms 162952 KB Output is correct
27 Correct 519 ms 163352 KB Output is correct
28 Correct 513 ms 160548 KB Output is correct
29 Correct 506 ms 160452 KB Output is correct
30 Correct 513 ms 160632 KB Output is correct