Submission #930543

#	Time	Username	Problem	Language	Result	Execution time	Memory
930543		dimashhh	Wall (IOI14_wall)	C++17	100 / 100	689 ms	138804 KiB

wall

#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 12, MOD = 998244353;

typedef long long ll;

#include "wall.h"

int mx[N * 4],mn[N * 4],_n,_mn[N * 4],_mx[N * 4],res[N];
void pull(int v,int val,bool ok){
    if(!ok){
        if(val >= mx[v]){
            mn[v] = _mn[v] = _mx[v] = mx[v] = val;
        }else if(val >= mn[v]){
            mn[v] = _mn[v] = val;
        }
    }else{
        if(val <= mn[v]){
            mn[v] = _mn[v] = _mx[v] = mx[v] = val;
        }else if(val <= mx[v]){
            mx[v] = _mx[v] = val;
        }
    }
//    cout << ok << ' ' << v << ' ' << _mn[v] << ' ' << _mx[v] << '\n';
}
void push(int v){
    if(_mn[v] != -1){
        mn[v + v] = _mn[v +v + 1] = mn[v + v + 1] = _mn[v + v] = _mn[v];
        _mn[v] = -1;
    }
    if(_mx[v] != -1){
        mx[v + v] = _mx[v +v + 1] = mx[v + v + 1] = _mx[v + v] = _mx[v];
        _mx[v] = -1;
    }
}
void upd(int l,int r,int val,bool ok,int v = 1,int tl = 1,int tr = _n){
//    cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << val << ' ' << ok << '\n';
    if(l > r || tl > r || l > tr) return;
//    cout << ok << "x\n";
    if(tl >= l && tr <= r && mx[v] - mn[v] <= 1){
//        cout << mn[v] << ' ' << mx[v] << '\n';
        pull(v,val,ok);
//        cout << tl << ' ' << tr << ' ' << mn[v] << ' ' << mx[v] << ' ' << ok << ' ' << _mn[v] << ' ' << _mx[v] << '\n';
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,val,ok,v+v,tl,tm);
        upd(l,r,val,ok,v+v+1,tm+1,tr);
        mn[v] = min(mn[v + v], mn[v + v + 1]);
        mx[v] = max(mx[v + v], mx[v + v + 1]);
    }
}
void go(int v = 1,int tl = 1,int tr = _n){
    if(tl == tr){
        res[tl - 1] = mn[v];
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        go(v+v,tl,tm);
        go(v+v+1,tm+1,tr);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    memset(_mn,-1,sizeof(_mn));
    memset(_mx, -1, sizeof(_mx));
    _n = n;
    for(int i = 0;i < k;i++){
        upd(left[i] + 1,right[i] + 1,height[i],(op[i] - 1));
    }
    go();
    for(int i = 0;i < n;i++){
        finalHeight[i] = res[i];
    }
    return;
}
//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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39