Submission #782705

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
782705	2023-07-14T08:04:46 Z	lollipop	Wall (IOI14_wall)	C++17	100 / 100	1153 ms	198596 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=1e6;
struct Node {
	long long 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	1 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	8 ms	1760 KB	Output is correct
5	Correct	8 ms	1756 KB	Output is correct
6	Correct	6 ms	1748 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	112 ms	8224 KB	Output is correct
3	Correct	60 ms	6372 KB	Output is correct
4	Correct	157 ms	19504 KB	Output is correct
5	Correct	169 ms	19984 KB	Output is correct
6	Correct	200 ms	19940 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	3 ms	340 KB	Output is correct
4	Correct	8 ms	1748 KB	Output is correct
5	Correct	8 ms	1748 KB	Output is correct
6	Correct	6 ms	1748 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	113 ms	8228 KB	Output is correct
9	Correct	61 ms	6396 KB	Output is correct
10	Correct	167 ms	19444 KB	Output is correct
11	Correct	179 ms	20028 KB	Output is correct
12	Correct	202 ms	19984 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	116 ms	8232 KB	Output is correct
15	Correct	33 ms	3532 KB	Output is correct
16	Correct	559 ms	19780 KB	Output is correct
17	Correct	323 ms	19676 KB	Output is correct
18	Correct	302 ms	19696 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	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	10 ms	1748 KB	Output is correct
5	Correct	8 ms	1756 KB	Output is correct
6	Correct	6 ms	1756 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	121 ms	8204 KB	Output is correct
9	Correct	63 ms	6480 KB	Output is correct
10	Correct	204 ms	19516 KB	Output is correct
11	Correct	175 ms	19904 KB	Output is correct
12	Correct	204 ms	19996 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	114 ms	8236 KB	Output is correct
15	Correct	33 ms	3576 KB	Output is correct
16	Correct	583 ms	19704 KB	Output is correct
17	Correct	358 ms	19708 KB	Output is correct
18	Correct	314 ms	19708 KB	Output is correct
19	Correct	1057 ms	198256 KB	Output is correct
20	Correct	1064 ms	195836 KB	Output is correct
21	Correct	1098 ms	198328 KB	Output is correct
22	Correct	1153 ms	196176 KB	Output is correct
23	Correct	1105 ms	196160 KB	Output is correct
24	Correct	1068 ms	196052 KB	Output is correct
25	Correct	1080 ms	196036 KB	Output is correct
26	Correct	1062 ms	198560 KB	Output is correct
27	Correct	1057 ms	198596 KB	Output is correct
28	Correct	1070 ms	196076 KB	Output is correct
29	Correct	1069 ms	195996 KB	Output is correct
30	Correct	1071 ms	196012 KB	Output is correct