oj.uz

Submission #943425

# Submission time Handle Problem Language Result Execution time Memory
943425 2024-03-11T13:07:50 Z pan Wall (IOI14_wall) C++17
61 / 100
 755 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 int 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 = 2e5;
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;
       l = r = nullptr;
    }
    
    void create()
    {
	   if (s!=e && l==nullptr)
       {
		   l = new node(s, m); 
		   r = new node(m+1, e);
	   }
	}

	void propogate()
	{
		if (s==e) return;
		create();
		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)
	{ 
       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 348 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 496 KB Output is correct
4 Correct 7 ms 2140 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 108 ms 11092 KB Output is correct
3 Correct 147 ms 7400 KB Output is correct
4 Correct 524 ms 26404 KB Output is correct
5 Correct 228 ms 27216 KB Output is correct
6 Correct 273 ms 26312 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 7 ms 1884 KB Output is correct
5 Correct 5 ms 1720 KB Output is correct
6 Correct 5 ms 1880 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 116 ms 11320 KB Output is correct
9 Correct 140 ms 8020 KB Output is correct
10 Correct 476 ms 26452 KB Output is correct
11 Correct 221 ms 27232 KB Output is correct
12 Correct 215 ms 26380 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 113 ms 11308 KB Output is correct
15 Correct 28 ms 3676 KB Output is correct
16 Correct 516 ms 26708 KB Output is correct
17 Correct 220 ms 26272 KB Output is correct
18 Correct 222 ms 26500 KB Output is correct

Subtask #4
0 / 39.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 1 ms 344 KB Output is correct
4 Correct 6 ms 1708 KB Output is correct
5 Correct 5 ms 1880 KB Output is correct
6 Correct 6 ms 1916 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 105 ms 11108 KB Output is correct
9 Correct 154 ms 8020 KB Output is correct
10 Correct 462 ms 26340 KB Output is correct
11 Correct 218 ms 27228 KB Output is correct
12 Correct 218 ms 26456 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 104 ms 11120 KB Output is correct
15 Correct 28 ms 3664 KB Output is correct
16 Correct 519 ms 26656 KB Output is correct
17 Correct 221 ms 26376 KB Output is correct
18 Correct 235 ms 26408 KB Output is correct
19 Runtime error 755 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -