Submission #31158

#	Time	Username	Problem	Language	Result	Execution time	Memory
31158		pasa3232	Wall (IOI14_wall)	C++14	100 / 100	1299 ms	95788 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF=1987654321;

struct A{
    int st, en;
    A operator+(const A &r){
        int x=max(r.st, st), y=min(r.en, en);
        if(x<=y) return (A){x, y};
        else if(x==r.st) return (A){x, x};
        else return (A){y, y};
    }
}tree[10000010];
int n, m;

void make_tree(int node, int s, int e){
    if(s==e){
        tree[node]=(A){0, INF};
        return;
    }
    int m=s+e>>1;
    make_tree(node*2, s, m);
    make_tree(node*2+1, m+1, e);
    tree[node]=tree[node*2]+tree[node*2+1];
}

void update(int node, int s, int e, int s1, int e1, A val){
    if(s>e1||e<s1) return;
    if(s1<=s&&e<=e1){
        tree[node]=tree[node]+val;
        return;
    }
    if(tree[node].st!=0||tree[node].en!=INF){
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]=(A){0, INF};
    }
    int m=s+e>>1;
    update(node*2, s, m, s1, e1, val);
    update(node*2+1, m+1, e, s1, e1, val);
}

A get(int node, int s, int e, int pos){
    if(s>pos||e<pos) return (A){0, INF};
    if(s==e){
        return tree[node];
    }
    if(tree[node].st!=0||tree[node].en!=INF){
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]=(A){0, INF};
    }
    int m=s+e>>1;
    return get(node*2, s, m, pos)+get(node*2+1, m+1, e, pos);
}

void buildWall(int N, int M, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N, m=M;
    make_tree(1, 0, n-1);
    for(int i=0; i<m; i++){
        int type=op[i], s=left[i], e=right[i], x=height[i];
        if(type==1){
            A rev=(A){x, INF};
            update(1, 0, n-1, s, e, rev);
        }
        else{
            A rev=(A){0, x};
            update(1, 0, n-1, s, e, rev);
        }
    }
    for(int i=0; i<n; i++) finalHeight[i]=get(1, 0, n-1, i).st;
}

Compilation message (stderr)

wall.cpp: In function 'void make_tree(int, int, int)':
wall.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
            ^
wall.cpp: In function 'void update(int, int, int, int, int, A)':
wall.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
            ^
wall.cpp: In function 'A get(int, int, int, int)':
wall.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
            ^

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