oj.uz

답안 #278054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278054 2020-08-21T09:25:23 Z mat_v 벽 (IOI14_wall) C++14
100 / 100
 1143 ms 130860 KB 
#include "wall.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 2000005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



int lazy[4 * maxn][2];
int seg[4 * maxn];

void propagate(int node, int l, int r){
    if(l == r){
        return;
    }
    if(lazy[node][0]){
        int val = lazy[node][0];
        seg[node] = max(seg[node], val);
        lazy[node * 2][0] = max(lazy[node * 2][0], val);
        seg[node * 2] = max(seg[node * 2], lazy[node * 2][0]);

        lazy[node * 2 + 1][0] = max(lazy[node * 2 + 1][0], val);
        seg[node * 2 + 1] = max(seg[node * 2 + 1], lazy[node * 2 + 1][0]);

        if(lazy[node * 2][0] > lazy[node * 2][1])lazy[node * 2][1] = lazy[node * 2][0];
        if(lazy[node * 2 + 1][0] > lazy[node * 2 + 1][1])lazy[node * 2 + 1][1] = lazy[node * 2 + 1][0];

        lazy[node][0] = 0;
    }
    if(lazy[node][1] < 1e9){
        int val = lazy[node][1];
        seg[node] = min(seg[node], val);
        lazy[node * 2][1] = min(lazy[node * 2][1], val);
        seg[node * 2] = min(seg[node * 2], lazy[node * 2][1]);

        lazy[node * 2 + 1][1] = min(lazy[node * 2 + 1][1], val);
        seg[node * 2 + 1] = min(seg[node * 2 + 1], lazy[node * 2 + 1][1]);

        if(lazy[node * 2][0] > lazy[node * 2][1])lazy[node * 2][0] = lazy[node * 2][1];
        if(lazy[node * 2 + 1][0] > lazy[node * 2 + 1][1])lazy[node * 2 + 1][0] = lazy[node * 2 + 1][1];

        lazy[node][1] = 1e9;


    }
}

void apdejt(int node, int l, int r, int levo, int desno, int h, int idx){
    //propagate(node, l, r);
    if(r < levo || l > desno)return;
    if(l >= levo && r <= desno){
        if(idx == 0){
            if(lazy[node][0] >= h)return;
            seg[node] = max(seg[node], h);
            lazy[node][0] = h;
            if(lazy[node][1] < lazy[node][0])lazy[node][1] = h;
        }
        else{
            if(lazy[node][1] <= h)return;
            seg[node] = min(seg[node], h);
            lazy[node][1] = h;
            if(lazy[node][1] < lazy[node][0])lazy[node][0] = h;
        }
        return;
    }
    propagate(node, l, r);
    int mid = (l + r) / 2;
    apdejt(node * 2, l, mid, levo, desno, h, idx);
    apdejt(node * 2 + 1, mid + 1, r, levo, desno, h, idx);
}

int query(int node, int l, int r, int poz){
    propagate(node, l, r);
    if(l == r)return seg[node];
    int mid = (l + r) / 2;
    if(poz <= mid)return query(node * 2, l, mid, poz);
    return query(node * 2 + 1, mid + 1, r, poz);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    ff(i,0,4 * n){
        lazy[i][0] = 0;
        lazy[i][1] = 1e9;
        seg[i] = 1;
    }
    ff(i,0,k - 1){
        int idx = op[i] - 1;
        int l = left[i] + 1;
        int r = right[i] + 1;
        int h = height[i] + 1;
        apdejt(1,1,n,l,r,h,idx);
    }
    ff(i,0,n - 1)finalHeight[i] = max(query(1,1,n,i+1) - 1,0);
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
wall.cpp:99:5: note: in expansion of macro 'ff'
   99 |     ff(i,0,4 * n){
      |     ^~
wall.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
wall.cpp:104:5: note: in expansion of macro 'ff'
  104 |     ff(i,0,k - 1){
      |     ^~
wall.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
wall.cpp:111:5: note: in expansion of macro 'ff'
  111 |     ff(i,0,n - 1)finalHeight[i] = max(query(1,1,n,i+1) - 1,0);
      |     ^~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 184 ms 8168 KB Output is correct
3 Correct 196 ms 4508 KB Output is correct
4 Correct 626 ms 13432 KB Output is correct
5 Correct 322 ms 13984 KB Output is correct
6 Correct 301 ms 13932 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 13 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 179 ms 8312 KB Output is correct
9 Correct 196 ms 4684 KB Output is correct
10 Correct 595 ms 13560 KB Output is correct
11 Correct 417 ms 13972 KB Output is correct
12 Correct 304 ms 14072 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 186 ms 8184 KB Output is correct
15 Correct 45 ms 1784 KB Output is correct
16 Correct 768 ms 13816 KB Output is correct
17 Correct 324 ms 13672 KB Output is correct
18 Correct 356 ms 13816 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 182 ms 8112 KB Output is correct
9 Correct 193 ms 4600 KB Output is correct
10 Correct 525 ms 13432 KB Output is correct
11 Correct 321 ms 14072 KB Output is correct
12 Correct 302 ms 13944 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 183 ms 8164 KB Output is correct
15 Correct 41 ms 1784 KB Output is correct
16 Correct 779 ms 13700 KB Output is correct
17 Correct 324 ms 13816 KB Output is correct
18 Correct 323 ms 13816 KB Output is correct
19 Correct 1143 ms 120312 KB Output is correct
20 Correct 1012 ms 128120 KB Output is correct
21 Correct 1080 ms 130632 KB Output is correct
22 Correct 1079 ms 128148 KB Output is correct
23 Correct 1070 ms 128120 KB Output is correct
24 Correct 1128 ms 128184 KB Output is correct
25 Correct 1123 ms 128248 KB Output is correct
26 Correct 1016 ms 130860 KB Output is correct
27 Correct 1136 ms 130628 KB Output is correct
28 Correct 994 ms 128248 KB Output is correct
29 Correct 1004 ms 128140 KB Output is correct
30 Correct 1094 ms 128120 KB Output is correct