Submission #653759

#	Time	Username	Problem	Language	Result	Execution time	Memory
653759		Lobo	Wall (IOI14_wall)	C++17	0 / 100	367 ms	126804 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int inf = 1e12+10;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

int n, trt[4*maxn], trb[4*maxn];
vector<int> qrsin[maxn], qrsout[maxn];

void att(int no, int l, int r, int pos, int valt, int valb) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trt[no] = valt;
        trb[no] = valb;
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    att(f1,l,mid,pos,valt,valb);
    att(f2,mid+1,r,pos,valt,valb);
    trt[no] = min(trt[f1],trt[f2]);
    trb[no] = max(trb[f1],trb[f2]);
}

// find the smallest i such that sfmnt[i] > sfmxb[i]
int findsf(int no, int l, int r, int valt, int valb) {
    if(l == r) {
        if(min(valt,trt[no]) > max(valb,trb[no])) return l;
        else return l+1;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    if(min(valt,trt[f2]) > max(valb,trb[f2])) return findsf(f1,l,mid,min(valt,trt[f2]),max(valb,trb[f2]));
    else return findsf(f2,mid+1,r,valt,valb);

}

void buildWall(int32_t N, int32_t k, int32_t op[], int32_t left[], int32_t right[], int32_t height[], int32_t finalHeight[]){
    n = N;
    for(int i = 0; i < k; i++) {
        qrsin[left[i]].pb(i);
        qrsout[right[i]].pb(i);
    }

    for(int i = 0; i < n; i++) {
        for(auto j : qrsin[i]) {
            if(op[j] == 1) att(1,0,k-1,j,height[j],-inf);
            if(op[j] == 2) att(1,0,k-1,j,inf,height[j]);
        }
        finalHeight[i] = height[findsf(1,0,k-1,inf,-inf)];
        for(auto j : qrsout[i]) {
            if(op[j] == 1) att(1,0,k-1,j,inf,-inf);
            if(op[j] == 2) att(1,0,k-1,j,inf,-inf);
        }
    }
}

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