oj.uz

Submission #742512

# Submission time Handle Problem Language Result Execution time Memory
742512 2023-05-16T11:13:52 Z Cookie Wall (IOI14_wall) C++14
0 / 100
 127 ms 8112 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e6 + 5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
#include "wall.h"
int mx[4 * mxn + 1], mn[4 * mxn + 1]; 
void push(int nd){
    mn[nd << 1] = min(mn[nd << 1], mn[nd]); mx[nd << 1] = min(mn[nd << 1], mx[nd << 1]);
    mx[nd << 1] = max(mx[nd], mx[nd << 1]); mn[nd << 1] = max(mn[nd << 1], mx[nd << 1]);
    mn[nd << 1 | 1] = min(mn[nd << 1 | 1], mn[nd]); mx[nd << 1 | 1] = min(mn[nd << 1 | 1], mx[nd << 1 | 1]);
    mx[nd << 1 | 1] = max(mx[nd], mx[nd << 1 | 1]); mn[nd << 1 | 1] = max(mx[nd << 1 | 1], mn[nd << 1 | 1]);
}
void add(int nd, int l, int r, int ql, int qr, int v){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        
        mx[nd] = max(mx[nd], v); mn[nd] = max(v, mx[nd]);
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    add(nd << 1, l, mid, ql, qr, v);
    add(nd << 1 | 1, mid + 1, r, ql, qr, v);
}
void rem(int nd, int l, int r, int ql, int qr, int v){
   
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        
        mn[nd] = min(mn[nd], v); mx[nd] = min(mx[nd], v);
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    rem(nd << 1, l, mid, ql, qr, v);
    rem(nd << 1 | 1, mid + 1, r, ql, qr, v);
}
int get(int nd, int l, int r, int id){
    if(l == r){
        return(min(mn[nd], mx[nd]));
    }
    push(nd);
    int mid = (l + r) >> 1;
    if(id <= mid){
        return(get(nd << 1, l, mid, id));
    }else{
        return(get(nd << 1 | 1, mid + 1, r, id));
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   for(int i = 1; i <= 4 * n; i++){
       mx[i] = 0; mn[i] = 1e9 + 1;
   }
   forr(i, 0, k){
       if(op[i] == 1)add(1, 0, n - 1, left[i], right[i], height[i]);
       else rem(1, 0, n - 1, left[i], right[i], height[i]);
   }
   forr(i, 0, n){
       finalHeight[i] = get(1, 0, n - 1, i);
   }
  return;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 126 ms 8112 KB Output is correct
3 Incorrect 127 ms 4196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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