oj.uz

Submission #943415

# Submission time Handle Problem Language Result Execution time Memory
943415 2024-03-11T13:05:44 Z pan Wall (IOI14_wall) C++17
61 / 100
 615 ms 262148 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;
       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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 6 ms 2140 KB Output is correct
5 Correct 5 ms 2140 KB Output is correct
6 Correct 7 ms 2140 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 111 ms 8260 KB Output is correct
3 Correct 170 ms 6576 KB Output is correct
4 Correct 567 ms 24400 KB Output is correct
5 Correct 227 ms 24968 KB Output is correct
6 Correct 245 ms 24992 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 2152 KB Output is correct
5 Correct 5 ms 2140 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 115 ms 8048 KB Output is correct
9 Correct 146 ms 6580 KB Output is correct
10 Correct 497 ms 24696 KB Output is correct
11 Correct 270 ms 24824 KB Output is correct
12 Correct 261 ms 24908 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 111 ms 8172 KB Output is correct
15 Correct 29 ms 3676 KB Output is correct
16 Correct 615 ms 24568 KB Output is correct
17 Correct 225 ms 24628 KB Output is correct
18 Correct 233 ms 24576 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 2140 KB Output is correct
5 Correct 5 ms 2140 KB Output is correct
6 Correct 5 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 109 ms 8020 KB Output is correct
9 Correct 166 ms 6444 KB Output is correct
10 Correct 528 ms 24504 KB Output is correct
11 Correct 224 ms 24876 KB Output is correct
12 Correct 221 ms 24816 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 128 ms 8476 KB Output is correct
15 Correct 41 ms 3676 KB Output is correct
16 Correct 575 ms 24576 KB Output is correct
17 Correct 281 ms 24660 KB Output is correct
18 Correct 239 ms 24656 KB Output is correct
19 Runtime error 612 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -