oj.uz

Submission #31808

# Submission time Handle Problem Language Result Execution time Memory
31808 2017-09-09T16:11:05 Z top34051 Wall (IOI14_wall) C++14
0 / 100
 196 ms 9844 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 105

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) {
    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) {
    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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Runtime error 0 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 196 ms 9844 KB Output is correct
3 Runtime error 93 ms 5416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Runtime error 0 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Runtime error 0 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -