Submission #782698

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
782698	2023-07-14T07:56:06 Z	lollipop	Wall (IOI14_wall)	C++17	100 / 100	1395 ms	167104 KB

wall

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
//const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "wall.h"
const int MAXN = 2000001;  // 1-based
int N;
int A[MAXN];
const int intINF=1e9+7;
struct Node {
	int sum;   // Sum tag
	int max1;  // Max value
	int max2;  // Second Max value
	int maxc;  // Max value count
	int min1;  // Min value
	int min2;  // Second Min value
	int minc;  // Min value count
	int lazy;  // Lazy tag
} T[MAXN * 4];
 
void merge(int t) {
	// sum
	T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;
 
	// max
	if (T[t << 1].max1 == T[t << 1 | 1].max1) {
		T[t].max1 = T[t << 1].max1;
		T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
		T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
	} else {
		if (T[t << 1].max1 > T[t << 1 | 1].max1) {
			T[t].max1 = T[t << 1].max1;
			T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
			T[t].maxc = T[t << 1].maxc;
		} else {
			T[t].max1 = T[t << 1 | 1].max1;
			T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
			T[t].maxc = T[t << 1 | 1].maxc;
		}
	}
 
	// min
	if (T[t << 1].min1 == T[t << 1 | 1].min1) {
		T[t].min1 = T[t << 1].min1;
		T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
		T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
	} else {
		if (T[t << 1].min1 < T[t << 1 | 1].min1) {
			T[t].min1 = T[t << 1].min1;
			T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
			T[t].minc = T[t << 1].minc;
		} else {
			T[t].min1 = T[t << 1 | 1].min1;
			T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
			T[t].minc = T[t << 1 | 1].minc;
		}
	}
}
 
void push_add(int t, int tl, int tr, int v) {
	if (v == 0) { return; }
	T[t].sum += (tr - tl + 1) * v;
	T[t].max1 += v;
	if (T[t].max2 != -intINF) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != intINF) { T[t].min2 += v; }
	T[t].lazy += v;
}
 
// corresponds to a chmin update
void push_max(int t, int v, bool l) {
	if (v >= T[t].max1) { return; }
	T[t].sum -= T[t].max1 * T[t].maxc;
	T[t].max1 = v;
	T[t].sum += T[t].max1 * T[t].maxc;
	if (l) {
		T[t].min1 = T[t].max1;
	} else {
		if (v <= T[t].min1) {
			T[t].min1 = v;
		} else if (v < T[t].min2) {
			T[t].min2 = v;
		}
	}
}
 
// corresponds to a chmax update
void push_min(int t, int v, bool l) {
	if (v <= T[t].min1) { return; }
	T[t].sum -= T[t].min1 * T[t].minc;
	T[t].min1 = v;
	T[t].sum += T[t].min1 * T[t].minc;
	if (l) {
		T[t].max1 = T[t].min1;
	} else {
		if (v >= T[t].max1) {
			T[t].max1 = v;
		} else if (v > T[t].max2) {
			T[t].max2 = v;
		}
	}
}
 
void pushdown(int t, int tl, int tr) {
	if (tl == tr) return;
	// sum
	int tm = (tl + tr) >> 1;
	push_add(t << 1, tl, tm, T[t].lazy);
	push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
	T[t].lazy = 0;
 
	// max
	push_max(t << 1, T[t].max1, tl == tm);
	push_max(t << 1 | 1, T[t].max1, tm + 1 == tr);
 
	// min
	push_min(t << 1, T[t].min1, tl == tm);
	push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}
 
void build(int t = 1, int tl = 0, int tr = N - 1) {
	T[t].lazy = 0;
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -intINF;
		T[t].min2 = intINF;
		return;
	}
 
	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
void update_add(int l, int r, int v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		push_add(t, tl, tr, v);
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_add(l, r, v, t << 1, tl, tm);
	update_add(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
void update_chmin(int l, int r, int v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v >= T[t].max1) { return; }
	if (l <= tl && tr <= r && v > T[t].max2) {
		push_max(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_chmin(l, r, v, t << 1, tl, tm);
	update_chmin(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
void update_chmax(int l, int r, int v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v <= T[t].min1) { return; }
	if (l <= tl && tr <= r && v < T[t].min2) {
		push_min(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_chmax(l, r, v, t << 1, tl, tm);
	update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
int query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return T[t].sum; }
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	return query_sum(l, r, t << 1, tl, tm) +
	       query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
void buildWall(int n, int k, int tp[], int l[], int r[], int h[], int finalHeight[]){
	N = n ; 
	 FOR( i , n ) A[ i ] = 0 ;
	 build() ;
	 FOR( i , k ){
	    int L = l[ i ] ; 
	    int R = r[ i ] ;
	    int H = h[ i ] ;
	 	if( tp[ i ] == 1 ){
	 	 	update_chmax(L, R, H);
		}
		else{
			update_chmin(L, R, H);
		}
	 }
	 FOR( i , n ) finalHeight[ i ] = query_sum( i , i ) ;
	 
}



//int main()
//{
//  int n;
//  int k;
//
//  int i, j;  
//  int status = 0;
//
//  status = scanf("%d%d", &n, &k);
//  assert(status == 2);
//
//  int* op = (int*)calloc(sizeof(int), k);
//  int* left = (int*)calloc(sizeof(int), k);
//  int* right = (int*)calloc(sizeof(int), k);
//  int* height = (int*)calloc(sizeof(int), k);
//  int* finalHeight = (int*)calloc(sizeof(int), n);
//
//  for (i = 0; i < k; i++){
//    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//    assert(status == 4);
//  }
//
//  buildWall(n, k, op, left, right, height, finalHeight);
//
//  for (j = 0; j < n; j++)
//    printf("%d\n", finalHeight[j]);
//  
//  return 0;
//}

Subtask #1

8.0 / 8.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	Correct	2 ms	340 KB	Output is correct
4	Correct	9 ms	1620 KB	Output is correct
5	Correct	7 ms	1592 KB	Output is correct
6	Correct	7 ms	1536 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	109 ms	8804 KB	Output is correct
3	Correct	61 ms	6564 KB	Output is correct
4	Correct	186 ms	18256 KB	Output is correct
5	Correct	177 ms	18640 KB	Output is correct
6	Correct	216 ms	18548 KB	Output is correct

Subtask #3

29.0 / 29.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	Correct	2 ms	328 KB	Output is correct
4	Correct	9 ms	1620 KB	Output is correct
5	Correct	7 ms	1608 KB	Output is correct
6	Correct	11 ms	1620 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	107 ms	8884 KB	Output is correct
9	Correct	61 ms	6476 KB	Output is correct
10	Correct	173 ms	18124 KB	Output is correct
11	Correct	182 ms	18580 KB	Output is correct
12	Correct	220 ms	18636 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	112 ms	8892 KB	Output is correct
15	Correct	45 ms	3620 KB	Output is correct
16	Correct	621 ms	18376 KB	Output is correct
17	Correct	343 ms	18352 KB	Output is correct
18	Correct	361 ms	18396 KB	Output is correct

Subtask #4

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	448 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	9 ms	1620 KB	Output is correct
5	Correct	7 ms	1620 KB	Output is correct
6	Correct	7 ms	1620 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	107 ms	8876 KB	Output is correct
9	Correct	61 ms	6604 KB	Output is correct
10	Correct	172 ms	18176 KB	Output is correct
11	Correct	182 ms	18636 KB	Output is correct
12	Correct	213 ms	18636 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	115 ms	8884 KB	Output is correct
15	Correct	36 ms	3628 KB	Output is correct
16	Correct	620 ms	18392 KB	Output is correct
17	Correct	340 ms	18400 KB	Output is correct
18	Correct	336 ms	18376 KB	Output is correct
19	Correct	1329 ms	167036 KB	Output is correct
20	Correct	1299 ms	164548 KB	Output is correct
21	Correct	1349 ms	167104 KB	Output is correct
22	Correct	1332 ms	164548 KB	Output is correct
23	Correct	1329 ms	164216 KB	Output is correct
24	Correct	1302 ms	164396 KB	Output is correct
25	Correct	1292 ms	164288 KB	Output is correct
26	Correct	1381 ms	166588 KB	Output is correct
27	Correct	1395 ms	166436 KB	Output is correct
28	Correct	1302 ms	163732 KB	Output is correct
29	Correct	1292 ms	163644 KB	Output is correct
30	Correct	1301 ms	163384 KB	Output is correct