oj.uz

Submission #722621

# Submission time Handle Problem Language Result Execution time Memory
722621 2023-04-12T12:54:22 Z penguin133 Wall (IOI14_wall) C++17
24 / 100
 737 ms 18544 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int s, e, m, val, mx, mn;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val = mx = 0 ;
		mn = 2e9;
	}
	
	void prop(){
		if(mx)val = max(val, mx);
		if(mn != 2e9)val = min(val, mn);
		if(s != e){
			if(mx)l->mx = max(mx, l->mx), r->mx = max(mx, r->mx);
			if(mn != 2e9)l->mn = min(l->mn, mn), r->mn = min(r->mn, mn);
		}
		mx = 0; mn = 2e9;
	}
	
	void upd(int a, int b, int c, bool d){
		//cerr << "UPD " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
		prop();
		if(a == s && b == e){
			if(!d)mx = max(mx, c);
			else mn = min(mn, c);
			return;
		}
		if(b <= m)l->upd(a, b, c, d);
		else if(a > m)r->upd(a, b, c, d);
		else l->upd(a, m, c, d), r->upd(m+1, b, c, d);
		l->prop(), r->prop();
		
	}
	
	int qry(int x){
		prop();
		if(s == e)return val;
		if(x <= m)return l->qry(x);
		else return r->qry(x);
	}
}*root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root = new node(0, n - 1);
	//cerr << "ok\n";
	for(int i=0;i<k;i++){
		if(op[i] == 1)root->upd(left[i], right[i], height[i], 0);
		else root->upd(left[i], right[i], height[i], 1);
		//cerr << "what\n";
	}
	//cerr << "ok\n";
	for(int i=0;i<n;i++)finalHeight[i] = root->qry(i);
}

Subtask #1
0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 156 ms 8084 KB Output is correct
3 Correct 218 ms 5340 KB Output is correct
4 Correct 737 ms 18124 KB Output is correct
5 Correct 344 ms 18544 KB Output is correct
6 Correct 279 ms 18508 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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