oj.uz

Submission #147273

# Submission time Handle Problem Language Result Execution time Memory
147273 2019-08-28T16:52:57 Z karma Wall (IOI14_wall) C++11
100 / 100
 857 ms 155276 KB 
#include<bits/stdc++.h>
#pragma GCC optimization("O3")

using namespace std;

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

struct TSegment{
     int n, low, high;
     vector<int> l, h;
     struct TNode {
         int Max, Min;
         TNode(int Max = 0, int Min = oo): Max(Max), Min(Min) {}
         bool operator==(const TNode& other) const&{
             return other.Max == Max && other.Min == Min;
         }
     } val;
     vector<TNode> st;
     TSegment(int n = 0): n(n) {
         st.resize(n << 2 | 1), l.resize(n << 2 | 1), h.resize(n << 2 | 1);
     }
     void Build(int x, int low, int high) {
          l[x] = low, h[x] = high, st[x] = TNode();
          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(l[x] == h[x] || st[x] == TNode()) return;
          TNode& lef = st[x << 1];
          TNode& rig = st[x << 1 | 1];
          lef.Max = max(lef.Max, st[x].Max);
          lef.Min = min(max(st[x].Max, lef.Min), st[x].Min);
          rig.Max = max(rig.Max, st[x].Max);
          rig.Min = min(max(st[x].Max, rig.Min), st[x].Min);
          st[x] = TNode();
     }
     void Update(int x) {
         if(l[x] > high || h[x] < low) return;
         if(l[x] >= low && h[x] <= high) {
             st[x].Max = max(val.Max, st[x].Max);
             st[x].Min = min(max(val.Max, st[x].Min), val.Min);
             Down(x);
             return;
         }
         Down(x);
         Update(x << 1); Update(x << 1 | 1);
     }
     void Update(int l, int h, int v, int type) {
         low = l, high = h;
         if(type == 1) val = TNode(v, oo);
         else val = TNode(0, v);
         Update(1);
     }
     void GetAns(int x, int ans[]) {
         if(l[x] == h[x]) {
           ans[l[x]] = min(st[x].Max, st[x].Min);
           //cout << l[x] << ' ' << st[x].Max << ' ' << st[x].Min << '\n';
           return;
         }
         Down(x);
         GetAns(x << 1, ans); GetAns(x << 1 | 1, ans);
     }
} 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) Irene.Update(lef[i], rig[i], h[i], op[i]);
     Irene.GetAns(1, ans);
}

//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] << ' ';
//}

Compilation message

wall.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 9 ms 1144 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 8 ms 1172 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 171 ms 11256 KB Output is correct
3 Correct 223 ms 8692 KB Output is correct
4 Correct 702 ms 22136 KB Output is correct
5 Correct 291 ms 18808 KB Output is correct
6 Correct 278 ms 17912 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 9 ms 1272 KB Output is correct
5 Correct 7 ms 1148 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 172 ms 11256 KB Output is correct
9 Correct 223 ms 8620 KB Output is correct
10 Correct 666 ms 17924 KB Output is correct
11 Correct 295 ms 18680 KB Output is correct
12 Correct 278 ms 17912 KB Output is correct
13 Correct 2 ms 128 KB Output is correct
14 Correct 174 ms 11400 KB Output is correct
15 Correct 39 ms 2552 KB Output is correct
16 Correct 672 ms 18296 KB Output is correct
17 Correct 285 ms 17912 KB Output is correct
18 Correct 287 ms 17912 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 9 ms 1272 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 173 ms 13036 KB Output is correct
9 Correct 221 ms 8568 KB Output is correct
10 Correct 666 ms 18396 KB Output is correct
11 Correct 292 ms 19064 KB Output is correct
12 Correct 285 ms 18292 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 13944 KB Output is correct
15 Correct 39 ms 2644 KB Output is correct
16 Correct 677 ms 18508 KB Output is correct
17 Correct 287 ms 18268 KB Output is correct
18 Correct 285 ms 18212 KB Output is correct
19 Correct 834 ms 155276 KB Output is correct
20 Correct 821 ms 152720 KB Output is correct
21 Correct 845 ms 155112 KB Output is correct
22 Correct 823 ms 152572 KB Output is correct
23 Correct 852 ms 152632 KB Output is correct
24 Correct 822 ms 152572 KB Output is correct
25 Correct 825 ms 152684 KB Output is correct
26 Correct 857 ms 155128 KB Output is correct
27 Correct 837 ms 155084 KB Output is correct
28 Correct 825 ms 152752 KB Output is correct
29 Correct 829 ms 152772 KB Output is correct
30 Correct 824 ms 152616 KB Output is correct