oj.uz

Submission #31810

# Submission time Handle Problem Language Result Execution time Memory
31810 2017-09-09T16:12:11 Z top34051 Wall (IOI14_wall) C++14
61 / 100
 1029 ms 87968 KB 
#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) {
    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 72328 KB Output is correct
2 Correct 0 ms 72464 KB Output is correct
3 Correct 0 ms 72328 KB Output is correct
4 Correct 6 ms 72464 KB Output is correct
5 Correct 6 ms 72464 KB Output is correct
6 Correct 6 ms 72464 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72328 KB Output is correct
2 Correct 206 ms 80152 KB Output is correct
3 Correct 286 ms 75724 KB Output is correct
4 Correct 713 ms 80544 KB Output is correct
5 Correct 433 ms 80544 KB Output is correct
6 Correct 443 ms 80544 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72328 KB Output is correct
2 Correct 0 ms 72464 KB Output is correct
3 Correct 0 ms 72328 KB Output is correct
4 Correct 6 ms 72464 KB Output is correct
5 Correct 6 ms 72464 KB Output is correct
6 Correct 6 ms 72464 KB Output is correct
7 Correct 0 ms 72328 KB Output is correct
8 Correct 186 ms 80152 KB Output is correct
9 Correct 283 ms 75724 KB Output is correct
10 Correct 776 ms 80544 KB Output is correct
11 Correct 529 ms 80544 KB Output is correct
12 Correct 409 ms 80544 KB Output is correct
13 Correct 0 ms 72328 KB Output is correct
14 Correct 186 ms 80152 KB Output is correct
15 Correct 43 ms 72956 KB Output is correct
16 Correct 773 ms 80544 KB Output is correct
17 Correct 409 ms 80544 KB Output is correct
18 Correct 466 ms 80544 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72328 KB Output is correct
2 Correct 0 ms 72464 KB Output is correct
3 Correct 0 ms 72328 KB Output is correct
4 Correct 6 ms 72464 KB Output is correct
5 Correct 13 ms 72464 KB Output is correct
6 Correct 6 ms 72464 KB Output is correct
7 Correct 0 ms 72328 KB Output is correct
8 Correct 189 ms 80152 KB Output is correct
9 Correct 239 ms 75724 KB Output is correct
10 Correct 776 ms 80544 KB Output is correct
11 Correct 469 ms 80544 KB Output is correct
12 Correct 486 ms 80544 KB Output is correct
13 Correct 0 ms 72328 KB Output is correct
14 Correct 199 ms 80152 KB Output is correct
15 Correct 53 ms 72956 KB Output is correct
16 Correct 806 ms 80544 KB Output is correct
17 Correct 479 ms 80544 KB Output is correct
18 Correct 433 ms 80544 KB Output is correct
19 Incorrect 1029 ms 87968 KB Output isn't correct
20 Halted 0 ms 0 KB -