oj.uz

Submission #943399

# Submission time Handle Problem Language Result Execution time Memory
943399 2024-03-11T13:00:00 Z pan Wall (IOI14_wall) C++17
61 / 100
 726 ms 262144 KB 
#include "wall.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, srb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll const INF = 1e13;
struct node{

    int s, e, m; 
    ll lower, upper;
    ll lazymin, lazymax;
    node *l, *r; 
	node (int S, int E)
	{ 
       s = S, e = E, m = (s+e)/2;
       lower= upper = 0;
       lazymin = INF, lazymax = -INF;
       if (s!=e)
       {
		   l = new node(s, m); 
		   r = new node(m+1, e);
	   }
    }

	void propogate()
	{
		if (s==e) return;
		if (lazymin!=INF) // minimum first
		{
			l->lazymax = min(l->lazymax, lazymin); // prevent max from overwriting min
			l->lazymin = min(l->lazymin, lazymin);
			l->lower = min(l->lower, lazymin);
			l->upper = min(l->upper, lazymin);
			
			r->lazymax = min(r->lazymax, lazymin); 
			r->lazymin = min(r->lazymin, lazymin);
			r->lower = min(r->lower, lazymin);
			r->upper = min(r->upper, lazymin);
			
			lazymin = INF;
		}
		if (lazymax!=-INF) // then maximum 
		{
			l->lazymax = max(l->lazymax, lazymax);
			l->lower = max(l->lower, lazymax);
			l->upper = max(l->upper, lazymax);
			
			r->lazymax = max(r->lazymax, lazymax);
			r->lower = max(r->lower, lazymax);
			r->upper = max(r->upper, lazymax);
			
			lazymax = -INF;
		}
    }
    
	void update(int S, int E, ll V, ll mm)
	{ 
	   propogate();
       if(s==S && e==E) 
       {
		   if (mm==2) // min
		   {
			   lazymax = min(lazymax, V);
		       lazymin = min(lazymin, V);
		       lower = min(lower, V);
			   upper = min(upper, V);
		       
		   }
		   else if (mm==1)// max
		   {
			   lazymax = max(lazymax, V);
			   lower = max(lower, V);
			   upper = max(upper, V);
		   }
	   }
       else
       { 
		   propogate();
           if(E <= m) l->update(S, E, V, mm); 
           else if (m < S) r->update(S, E, V, mm); 
           else l->update(S, m, V, mm),r->update(m+1, E, V, mm);
		   lower = min(l->lower, r->lower);
           upper = max(l->upper, r->upper);
       }
    }
	ll query(ll pos)
	{ 
		if (s==e) return upper;
		propogate();
		if (pos<=m) return l->query(pos);
		else return r->query(pos);
    }

} *root;
 


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	root = new node(0, n-1);
	for (ll i=0; i<k; ++i) root->update(left[i], right[i], height[i], op[i]);
	for (ll i=0; i<n; ++i) finalHeight[i] = root->query(i);
	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 2140 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 5 ms 2140 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 110 ms 13908 KB Output is correct
3 Correct 191 ms 9040 KB Output is correct
4 Correct 582 ms 34036 KB Output is correct
5 Correct 246 ms 35136 KB Output is correct
6 Correct 243 ms 33376 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 2136 KB Output is correct
5 Correct 6 ms 2140 KB Output is correct
6 Correct 7 ms 2424 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 112 ms 13872 KB Output is correct
9 Correct 165 ms 10432 KB Output is correct
10 Correct 636 ms 34232 KB Output is correct
11 Correct 253 ms 35156 KB Output is correct
12 Correct 248 ms 33432 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 111 ms 13856 KB Output is correct
15 Correct 33 ms 4176 KB Output is correct
16 Correct 682 ms 34248 KB Output is correct
17 Correct 249 ms 33736 KB Output is correct
18 Correct 245 ms 33620 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 2140 KB Output is correct
5 Correct 6 ms 2200 KB Output is correct
6 Correct 5 ms 2104 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 108 ms 13940 KB Output is correct
9 Correct 181 ms 10324 KB Output is correct
10 Correct 620 ms 34032 KB Output is correct
11 Correct 250 ms 34984 KB Output is correct
12 Correct 270 ms 33616 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 111 ms 13908 KB Output is correct
15 Correct 33 ms 4176 KB Output is correct
16 Correct 726 ms 34360 KB Output is correct
17 Correct 254 ms 33620 KB Output is correct
18 Correct 252 ms 34132 KB Output is correct
19 Runtime error 351 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -