Submission #990234

#	Time	Username	Problem	Language	Result	Execution time	Memory
990234		aaaaaarroz	Wall (IOI14_wall)	C++17	100 / 100	341 ms	176716 KiB

wall

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = (1 << 22);
const int mod = 1e9 + 7;
const int inf = INT_MAX;
using namespace std;
struct event{
    int ty,op,id,val;
};
vector<event>q[mxN];
pii seg[mxN];
int N,s,e;
pii combine(pii a,pii b){
    pii c = a;
    c.F = min(c.F,b.S);
    c.F = max(c.F,b.F);
    c.S = min(a.S,b.S);
    return c;
}
void update(int ind,pii val){
    ind += N;
    seg[ind] = val;
    while(ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    // N = exp2(ceil(log2(n)));
    N = 1 << 20;
    for(int i = 1;i < N * 2;i++){
        seg[i] = {0,inf};
    }
    for(int i = 0;i < k;i++){
        q[left[i]].push_back({1,op[i],i,height[i]});
        q[right[i] + 1].push_back({-1,op[i],i,height[i]});
    }
    for(int i = 0;i < n;i++){
        while(q[i].size()){
            auto u = q[i].back();
            q[i].pop_back();
            if(u.ty == -1){
                update(u.id,{0,inf});
            }else{
                if(u.op == 1) update(u.id,{u.val,inf});
                else update(u.id, {0,u.val});
            }
        }
        finalHeight[i] = seg[1].F;
    }
}

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