oj.uz

Submission #278037

# Submission time Handle Problem Language Result Execution time Memory
278037 2020-08-21T09:10:30 Z mat_v Wall (IOI14_wall) C++14
24 / 100
 780 ms 25592 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]);
        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]);
        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;
        }
        propagate(node, l, r);
        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:89:5: note: in expansion of macro 'ff'
   89 |     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:94:5: note: in expansion of macro 'ff'
   94 |     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:101:5: note: in expansion of macro 'ff'
  101 |     ff(i,0,n - 1)finalHeight[i] = max(query(1,1,n,i+1) - 1,0);
      |     ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 188 ms 14044 KB Output is correct
3 Correct 279 ms 9208 KB Output is correct
4 Correct 780 ms 24628 KB Output is correct
5 Correct 439 ms 25592 KB Output is correct
6 Correct 373 ms 24064 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -