Submission #785607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785607	2023-07-17T10:35:31 Z	lollipop	Wall (IOI14_wall)	C++17	100 / 100	1365 ms	175856 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	1 ms	212 KB	Output is correct
2	Correct	2 ms	452 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	8 ms	1596 KB	Output is correct
5	Correct	7 ms	1620 KB	Output is correct
6	Correct	7 ms	1612 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	114 ms	13900 KB	Output is correct
3	Correct	63 ms	9600 KB	Output is correct
4	Correct	167 ms	26860 KB	Output is correct
5	Correct	188 ms	28056 KB	Output is correct
6	Correct	218 ms	26404 KB	Output is correct

Subtask #3

29.0 / 29.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	9 ms	1532 KB	Output is correct
5	Correct	7 ms	1620 KB	Output is correct
6	Correct	7 ms	1620 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	109 ms	13900 KB	Output is correct
9	Correct	63 ms	9544 KB	Output is correct
10	Correct	169 ms	26972 KB	Output is correct
11	Correct	180 ms	27964 KB	Output is correct
12	Correct	217 ms	26316 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	118 ms	13868 KB	Output is correct
15	Correct	36 ms	3628 KB	Output is correct
16	Correct	616 ms	27132 KB	Output is correct
17	Correct	340 ms	26556 KB	Output is correct
18	Correct	339 ms	26560 KB	Output is correct

Subtask #4

39.0 / 39.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	328 KB	Output is correct
4	Correct	8 ms	1620 KB	Output is correct
5	Correct	7 ms	1596 KB	Output is correct
6	Correct	7 ms	1640 KB	Output is correct
7	Correct	1 ms	320 KB	Output is correct
8	Correct	108 ms	13832 KB	Output is correct
9	Correct	76 ms	9524 KB	Output is correct
10	Correct	170 ms	27020 KB	Output is correct
11	Correct	192 ms	27956 KB	Output is correct
12	Correct	215 ms	26372 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	116 ms	13968 KB	Output is correct
15	Correct	36 ms	3536 KB	Output is correct
16	Correct	619 ms	27132 KB	Output is correct
17	Correct	343 ms	26560 KB	Output is correct
18	Correct	355 ms	26596 KB	Output is correct
19	Correct	1303 ms	175844 KB	Output is correct
20	Correct	1313 ms	173232 KB	Output is correct
21	Correct	1321 ms	175796 KB	Output is correct
22	Correct	1350 ms	173312 KB	Output is correct
23	Correct	1303 ms	173344 KB	Output is correct
24	Correct	1313 ms	173320 KB	Output is correct
25	Correct	1365 ms	173252 KB	Output is correct
26	Correct	1327 ms	175848 KB	Output is correct
27	Correct	1312 ms	175856 KB	Output is correct
28	Correct	1301 ms	173324 KB	Output is correct
29	Correct	1303 ms	173304 KB	Output is correct
30	Correct	1333 ms	173260 KB	Output is correct