oj.uz

Submission #241295

# Submission time Handle Problem Language Result Execution time Memory
241295 2020-06-23T17:51:28 Z Mercenary Wall (IOI14_wall) C++14
100 / 100
 794 ms 91388 KB 
#include "wall.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e6 + 5;

int mx[maxn * 4] , mn[maxn * 4];
int lz[maxn * 4];

void push(int x , bool key){
    if(lz[x] != -1){
        mx[x] = mn[x] = lz[x];
        if(key)lz[x * 2] = lz[x * 2 + 1] = lz[x];
    }
    lz[x] = -1;
}

void upMin(int x , int l , int r , int L , int R , int val){
    push(x , l != r);
    if(l > R || L > r || mx[x] <= val)return;
    if(L <= l && r <= R && mn[x] >= val){
        lz[x] = val;push(x , l != r);
        return;
    }
    int mid = l + r >> 1;
    upMin(x * 2,  l , mid , L , R , val);
    upMin(x * 2 + 1 , mid + 1 , r , L , R , val);
    mx[x] = max(mx[x * 2] , mx[x * 2+ 1]);
    mn[x] = min(mn[x * 2] , mn[x * 2 + 1]);
}

void upMax(int x , int l , int r , int L , int R , int val){
    push(x , l != r);
    if(l > R || L > r || mn[x] >= val)return;
    if(L <= l && r <= R && mx[x] <= val){
        lz[x] = val;push(x , l != r);
        return;
    }
    int mid = l + r >> 1;
    upMax(x * 2,  l , mid , L , R , val);
    upMax(x * 2 + 1 , mid + 1 , r , L , R , val);
    mx[x] = max(mx[x * 2] , mx[x * 2+ 1]);
    mn[x] = min(mn[x * 2] , mn[x * 2 + 1]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    memset(lz,-1,sizeof lz);
    for(int i = 0 ; i < k ; ++i){
        if(op[i] == 1)upMax(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);
        else upMin(1 , 1 , n , left[i] + 1,  right[i] + 1 , height[i]);
    }
    function<void(int,int,int)> GetAns = [&](int x , int l , int r)->void{
        push(x , l != r);
        if(l == r){
            finalHeight[l - 1] = mx[x];
            return;
        }
        int mid = l + r >> 1;
        GetAns(x * 2 , l , mid);
        GetAns(x * 2 + 1 , mid + 1 , r);
    };
    GetAns(1 , 1 , n);
}

//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    if(fopen(taskname".INP","r")){
//		freopen(taskname".INP", "r",stdin);
//		freopen(taskname".OUT", "w",stdout);
//    }
//
//}

Compilation message

wall.cpp: In function 'void upMin(int, int, int, int, int, int)':
wall.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
wall.cpp: In function 'void upMax(int, int, int, int, int, int)':
wall.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
wall.cpp: In lambda function:
wall.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31616 KB Output is correct
2 Correct 23 ms 31872 KB Output is correct
3 Correct 22 ms 31744 KB Output is correct
4 Correct 28 ms 32128 KB Output is correct
5 Correct 26 ms 32128 KB Output is correct
6 Correct 27 ms 32128 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31616 KB Output is correct
2 Correct 194 ms 40440 KB Output is correct
3 Correct 117 ms 36728 KB Output is correct
4 Correct 251 ms 43256 KB Output is correct
5 Correct 239 ms 43768 KB Output is correct
6 Correct 258 ms 43768 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 24 ms 31736 KB Output is correct
3 Correct 23 ms 31744 KB Output is correct
4 Correct 26 ms 32128 KB Output is correct
5 Correct 25 ms 32256 KB Output is correct
6 Correct 26 ms 32128 KB Output is correct
7 Correct 21 ms 31616 KB Output is correct
8 Correct 195 ms 40568 KB Output is correct
9 Correct 117 ms 36728 KB Output is correct
10 Correct 263 ms 43256 KB Output is correct
11 Correct 249 ms 43780 KB Output is correct
12 Correct 256 ms 43896 KB Output is correct
13 Correct 23 ms 31616 KB Output is correct
14 Correct 198 ms 40568 KB Output is correct
15 Correct 52 ms 33400 KB Output is correct
16 Correct 514 ms 43608 KB Output is correct
17 Correct 329 ms 43516 KB Output is correct
18 Correct 357 ms 43512 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31616 KB Output is correct
2 Correct 21 ms 31744 KB Output is correct
3 Correct 23 ms 31744 KB Output is correct
4 Correct 26 ms 32128 KB Output is correct
5 Correct 25 ms 32128 KB Output is correct
6 Correct 25 ms 32128 KB Output is correct
7 Correct 21 ms 31616 KB Output is correct
8 Correct 192 ms 40440 KB Output is correct
9 Correct 119 ms 36600 KB Output is correct
10 Correct 258 ms 43128 KB Output is correct
11 Correct 241 ms 43640 KB Output is correct
12 Correct 252 ms 43896 KB Output is correct
13 Correct 20 ms 31616 KB Output is correct
14 Correct 196 ms 40568 KB Output is correct
15 Correct 50 ms 33392 KB Output is correct
16 Correct 533 ms 43384 KB Output is correct
17 Correct 342 ms 43256 KB Output is correct
18 Correct 359 ms 43244 KB Output is correct
19 Correct 748 ms 91384 KB Output is correct
20 Correct 747 ms 89080 KB Output is correct
21 Correct 770 ms 91384 KB Output is correct
22 Correct 740 ms 88968 KB Output is correct
23 Correct 754 ms 88952 KB Output is correct
24 Correct 751 ms 88728 KB Output is correct
25 Correct 762 ms 88828 KB Output is correct
26 Correct 752 ms 91260 KB Output is correct
27 Correct 738 ms 91388 KB Output is correct
28 Correct 740 ms 88568 KB Output is correct
29 Correct 794 ms 88612 KB Output is correct
30 Correct 776 ms 88628 KB Output is correct