Submission #147273

#	Time	Username	Problem	Language	Result	Execution time	Memory
147273		karma	Wall (IOI14_wall)	C++11	100 / 100	857 ms	155276 KiB

wall

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

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

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39