oj.uz

Submission #31809

# Submission time Handle Problem Language Result Execution time Memory
31809 2017-09-09T16:11:27 Z top34051 Wall (IOI14_wall) C++14
61 / 100
 876 ms 52812 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005

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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37172 KB Output is correct
2 Correct 0 ms 37308 KB Output is correct
3 Correct 0 ms 37172 KB Output is correct
4 Correct 6 ms 37308 KB Output is correct
5 Correct 3 ms 37308 KB Output is correct
6 Correct 3 ms 37308 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37172 KB Output is correct
2 Correct 166 ms 44996 KB Output is correct
3 Correct 293 ms 40568 KB Output is correct
4 Correct 876 ms 45388 KB Output is correct
5 Correct 516 ms 45388 KB Output is correct
6 Correct 489 ms 45388 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37172 KB Output is correct
2 Correct 0 ms 37308 KB Output is correct
3 Correct 0 ms 37172 KB Output is correct
4 Correct 3 ms 37308 KB Output is correct
5 Correct 9 ms 37308 KB Output is correct
6 Correct 9 ms 37308 KB Output is correct
7 Correct 0 ms 37172 KB Output is correct
8 Correct 196 ms 44996 KB Output is correct
9 Correct 266 ms 40568 KB Output is correct
10 Correct 769 ms 45388 KB Output is correct
11 Correct 499 ms 45388 KB Output is correct
12 Correct 489 ms 45388 KB Output is correct
13 Correct 0 ms 37172 KB Output is correct
14 Correct 183 ms 44996 KB Output is correct
15 Correct 43 ms 37800 KB Output is correct
16 Correct 746 ms 45388 KB Output is correct
17 Correct 429 ms 45388 KB Output is correct
18 Correct 386 ms 45388 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37172 KB Output is correct
2 Correct 0 ms 37308 KB Output is correct
3 Correct 3 ms 37172 KB Output is correct
4 Correct 6 ms 37308 KB Output is correct
5 Correct 6 ms 37308 KB Output is correct
6 Correct 6 ms 37308 KB Output is correct
7 Correct 0 ms 37172 KB Output is correct
8 Correct 179 ms 44996 KB Output is correct
9 Correct 243 ms 40568 KB Output is correct
10 Correct 749 ms 45388 KB Output is correct
11 Correct 529 ms 45388 KB Output is correct
12 Correct 449 ms 45388 KB Output is correct
13 Correct 0 ms 37172 KB Output is correct
14 Correct 179 ms 44996 KB Output is correct
15 Correct 43 ms 37800 KB Output is correct
16 Correct 793 ms 45388 KB Output is correct
17 Correct 436 ms 45388 KB Output is correct
18 Correct 453 ms 45388 KB Output is correct
19 Runtime error 236 ms 52812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -