Submission #241295

#	Time	Username	Problem	Language	Result	Execution time	Memory
241295		Mercenary	Wall (IOI14_wall)	C++14	100 / 100	794 ms	91388 KiB

wall

#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 (stderr)

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39