oj.uz

Submission #147260

# Submission time Handle Problem Language Result Execution time Memory
147260 2019-08-28T14:24:53 Z karma Wall (IOI14_wall) C++11
0 / 100
 1137 ms 24696 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = int(2e6) + 7;
const int oo = int(1e9) + 7;

struct TSegment{
     int n, low, high, val;
     vector<int> st, lazy, l, h;
     TSegment(int n = 0): n(n) {
         st.resize(4 * n), lazy.resize(4 * n), l.resize(4 * n), h.resize(4 * n);
     }
     void Build(int x, int low, int high) {
          l[x] = low, h[x] = high, st[x] = 0, lazy[x] = -oo;
          if(l[x] == h[x]) return;
          int mid = (low + high) >> 1;
          Build(x << 1, low, mid); Build(x << 1 | 1, mid + 1, high);
     }
     void Down(int x) {
          if(lazy[x] == -oo || l[x] == h[x]) {lazy[x] = -oo; return;}
          if(st[x << 1] * lazy[x] < 0) st[x << 1] = lazy[x];
          else st[x << 1] = max(st[x << 1], lazy[x]);
          if(lazy[x << 1] * lazy[x] < 0) lazy[x << 1] = lazy[x];
          else lazy[x << 1] = max(lazy[x << 1], lazy[x]);
          if(st[x << 1 | 1] * lazy[x] < 0) st[x << 1 | 1] = lazy[x];
          else st[x << 1 | 1] = max(st[x << 1 | 1], lazy[x]);
          if(lazy[x << 1 | 1] * lazy[x] < 0) lazy[x << 1 | 1] = lazy[x];
          else lazy[x << 1 | 1] = max(lazy[x << 1 | 1], lazy[x]);
          lazy[x] = -oo;
     }
     void Update(int x) {
         Down(x);
         if(l[x] > high || h[x] < low) return;
         if(l[x] >= low && h[x] <= high) {
             if(st[x] * val < 0) st[x] = val;
             else st[x] = max(st[x], val);
             lazy[x] = max(lazy[x], val);
             return;
         }
         Update(x << 1); Update(x << 1 | 1);
         st[x] = max(st[x << 1], st[x << 1 | 1]);
     }
     void Update(int l, int h, int v) {
         low = l, high = h, val = v;
         Update(1);
     }
     int Query(int x, int pos) {
         Down(x);
         if(l[x] > pos || h[x] < pos) return -oo;
         if(l[x] == pos && h[x] == pos) return st[x];
         return max(Query(x << 1, pos), Query(x << 1 | 1, pos));
     }
} Irene;

void buildWall(int n, int k, int op[], int lef[], int rig[], int h[], int ans[])
{
     Irene = TSegment(n);
     Irene.Build(1, 0, n - 1);
     for(int i = 0; i < k; ++i) {
        if(op[i] == 1) Irene.Update(lef[i], rig[i], h[i]);
        else Irene.Update(lef[i], rig[i], -h[i]);
     }
     for(int i = 0; i < n; ++i) ans[i] = abs(Irene.Query(1, i));
}
/*
int _n, _k, _op[N], _lef[N], _rig[N], _h[N], ans[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> _n >> _k;
    for(int i = 0; i < _k; ++i) cin >> _op[i] >> _lef[i] >> _rig[i] >> _h[i];
    buildWall(_n, _k, _op, _lef, _rig, _h, ans);
    for(int i = 0; i < _n; ++i) cout << ans[i] << ' ';
}
*/

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 174 ms 14024 KB Output is correct
3 Correct 415 ms 8568 KB Output is correct
4 Incorrect 1137 ms 24696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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