Submission #278037

#	Time	Username	Problem	Language	Result	Execution time	Memory
278037		mat_v	Wall (IOI14_wall)	C++14	24 / 100	780 ms	25592 KiB

wall

#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 (stderr)

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
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39