Submission #31811

#	Time	Username	Problem	Language	Result	Execution time	Memory
31811		top34051	Wall (IOI14_wall)	C++14	100 / 100	1036 ms	87968 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000005

int ans[maxn];
int L[maxn*4], R[maxn*4];

void upd(int pos,int l,int r) {
    L[pos] = max(L[pos], l);
    L[pos] = min(L[pos], r);
    R[pos] = max(R[pos], l);
    R[pos] = min(R[pos], r);
}

void update(int pos,int l,int r,int x,int y,int val,int type) {
    if(l!=r) {
        upd(pos<<1,L[pos],R[pos]);
        upd(pos<<1|1,L[pos],R[pos]);
    }
    if(l>r || y<l || r<x) return ;
    if(x<=l && r<=y) {
        if(type==1) {
            L[pos] = max(L[pos], val);
            R[pos] = max(R[pos], val);
        }
        else {
            L[pos] = min(L[pos], val);
            R[pos] = min(R[pos], val);
        }
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,y,val,type); update(pos<<1|1,mid+1,r,x,y,val,type);
    L[pos] = min(L[pos<<1], L[pos<<1|1]);
    R[pos] = max(R[pos<<1], R[pos<<1|1]);
}

void query(int pos,int l,int r) {
    if(l!=r) {
        upd(pos<<1,L[pos],R[pos]);
        upd(pos<<1|1,L[pos],R[pos]);
    }
    if(l==r) {
        ans[l] = L[pos];
        return ;
    }
    int mid = (l+r)/2;
    query(pos<<1,l,mid); query(pos<<1|1,mid+1,r);
}

void buildWall(int n, int m, int type[], int l[], int r[], int val[], int ret[]) {
    int i;
    for(i=0;i<m;i++) update(1,0,n-1,l[i],r[i],val[i],type[i]);
    query(1,0,n-1);
    for(i=0;i<n;i++) ret[i] = ans[i];
    return ;
}

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