| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 782696 |
2023-07-14T07:54:57 Z |
lollipop |
Wall (IOI14_wall) |
C++17 |
|
5 ms |
552 KB |
#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[]){
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;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
544 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
552 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
552 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
