Submission #453664

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
453664	2021-08-04 13:54:31	ponytail	Wall (IOI14_wall)	C++17	100 / 100	1451 ms	77524 KiB

wall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAXN = 2e6 + 10;
struct node{
    int Min, Max;
} a[4*MAXN];
void update(int l,int r,int constl,int constr,int idx,int val,string type){
    if(l<=constl && constr<=r){
        if(type == "ADD"){
            a[idx].Min = max(a[idx].Min, val);
            a[idx].Max = max(a[idx].Max, val);
        }
        else{
            a[idx].Min = min(a[idx].Min, val);
            a[idx].Max = min(a[idx].Max, val);
        }
        return;
    }
    int mid = (constl+constr)/2;
    //Lazy propagation: Remember to return a[idx].Min and a[idx].Max into initial state
    a[2*idx+1].Min = max(a[2*idx+1].Min, a[idx].Max);
    a[2*idx+1].Max = max(a[2*idx+1].Max, a[idx].Max);
    a[2*idx+2].Min = max(a[2*idx+2].Min, a[idx].Max);
    a[2*idx+2].Max = max(a[2*idx+2].Max, a[idx].Max);
    a[2*idx+1].Min = min(a[2*idx+1].Min, a[idx].Min);
    a[2*idx+1].Max = min(a[2*idx+1].Max, a[idx].Min);
    a[2*idx+2].Min = min(a[2*idx+2].Min, a[idx].Min);
    a[2*idx+2].Max = min(a[2*idx+2].Max, a[idx].Min);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39