oj.uz

Submission #278052

# Submission time Handle Problem Language Result Execution time Memory
278052 2020-08-21T09:24:13 Z mat_v Wall (IOI14_wall) C++14
61 / 100
 938 ms 231624 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];
int niz[maxn];
bool treba[4 * maxn];

void propagate(int node, int l, int r){
    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:98:5: note: in expansion of macro 'ff'
   98 |     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:103:5: note: in expansion of macro 'ff'
  103 |     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:110:5: note: in expansion of macro 'ff'
  110 |     ff(i,0,n - 1)finalHeight[i] = max(query(1,1,n,i+1) - 1,0);
      |     ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory 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 11 ms 1408 KB Output is correct
5 Correct 7 ms 1408 KB Output is correct
6 Correct 7 ms 1408 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 189 ms 8264 KB Output is correct
3 Correct 189 ms 5280 KB Output is correct
4 Correct 591 ms 15096 KB Output is correct
5 Correct 337 ms 15608 KB Output is correct
6 Correct 326 ms 15484 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory 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 1568 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 7 ms 1408 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 182 ms 14072 KB Output is correct
9 Correct 193 ms 9080 KB Output is correct
10 Correct 550 ms 24696 KB Output is correct
11 Correct 329 ms 25592 KB Output is correct
12 Correct 313 ms 24056 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 188 ms 14072 KB Output is correct
15 Correct 48 ms 3096 KB Output is correct
16 Correct 769 ms 24932 KB Output is correct
17 Correct 330 ms 24280 KB Output is correct
18 Correct 343 ms 24288 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory 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 11 ms 1408 KB Output is correct
5 Correct 8 ms 1408 KB Output is correct
6 Correct 7 ms 1408 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 184 ms 14072 KB Output is correct
9 Correct 209 ms 9192 KB Output is correct
10 Correct 598 ms 24696 KB Output is correct
11 Correct 334 ms 25720 KB Output is correct
12 Correct 306 ms 24056 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 190 ms 14028 KB Output is correct
15 Correct 46 ms 3064 KB Output is correct
16 Correct 754 ms 24952 KB Output is correct
17 Correct 375 ms 24184 KB Output is correct
18 Correct 332 ms 24184 KB Output is correct
19 Runtime error 938 ms 231624 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -