oj.uz

답안 #31811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31811 2017-09-09T16:14:16 Z top34051 벽 (IOI14_wall) C++14
100 / 100
 1036 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) {
    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.0 / 8.0

# 결과 실행 시간 메모리 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 3 ms 72464 KB Output is correct
6 Correct 3 ms 72464 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 72328 KB Output is correct
2 Correct 153 ms 80152 KB Output is correct
3 Correct 269 ms 75724 KB Output is correct
4 Correct 673 ms 80544 KB Output is correct
5 Correct 436 ms 80544 KB Output is correct
6 Correct 446 ms 80544 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 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 3 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 253 ms 75724 KB Output is correct
10 Correct 773 ms 80544 KB Output is correct
11 Correct 479 ms 80544 KB Output is correct
12 Correct 436 ms 80544 KB Output is correct
13 Correct 0 ms 72328 KB Output is correct
14 Correct 169 ms 80152 KB Output is correct
15 Correct 43 ms 72956 KB Output is correct
16 Correct 739 ms 80544 KB Output is correct
17 Correct 433 ms 80544 KB Output is correct
18 Correct 433 ms 80544 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 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 3 ms 72464 KB Output is correct
5 Correct 3 ms 72464 KB Output is correct
6 Correct 3 ms 72464 KB Output is correct
7 Correct 0 ms 72328 KB Output is correct
8 Correct 183 ms 80152 KB Output is correct
9 Correct 276 ms 75724 KB Output is correct
10 Correct 769 ms 80544 KB Output is correct
11 Correct 419 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 196 ms 80152 KB Output is correct
15 Correct 39 ms 72956 KB Output is correct
16 Correct 799 ms 80544 KB Output is correct
17 Correct 433 ms 80544 KB Output is correct
18 Correct 453 ms 80544 KB Output is correct
19 Correct 996 ms 87968 KB Output is correct
20 Correct 949 ms 87968 KB Output is correct
21 Correct 906 ms 87968 KB Output is correct
22 Correct 903 ms 87968 KB Output is correct
23 Correct 889 ms 87968 KB Output is correct
24 Correct 926 ms 87968 KB Output is correct
25 Correct 983 ms 87968 KB Output is correct
26 Correct 933 ms 87968 KB Output is correct
27 Correct 1036 ms 87968 KB Output is correct
28 Correct 869 ms 87968 KB Output is correct
29 Correct 1018 ms 87968 KB Output is correct
30 Correct 936 ms 87968 KB Output is correct