oj.uz

Submission #239215

# Submission time Handle Problem Language Result Execution time Memory
239215 2020-06-14T20:09:25 Z aggu_01000101 Wall (IOI14_wall) C++14
100 / 100
 1372 ms 135440 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
const int N = 2000005;
int seg[4*N];
pair<int, int> lazy[4*N];
int build(int l, int u, int i){
    lazy[i] = {-INF, INF};
    if(l==u) return seg[i] = 0;
    return seg[i] = min(build(l, mid(l, u), lchild(i)), build(mid(l, u)+1, u, rchild(i)));
}
int query(int l, int u, int i, int ll, int uu){
    if(lazy[i].second != INF || lazy[i].first != -INF){
        seg[i] = min(seg[i], lazy[i].second);
        seg[i] = max(seg[i], lazy[i].first);
        if(l!=u){
            lazy[lchild(i)].second = min(lazy[lchild(i)].second, lazy[i].second);
            lazy[lchild(i)].first = min(lazy[lchild(i)].first, lazy[i].second);
            lazy[lchild(i)].first = max(lazy[lchild(i)].first, lazy[i].first);
            lazy[lchild(i)].second = max(lazy[lchild(i)].second, lazy[i].first);

            lazy[rchild(i)].second = min(lazy[rchild(i)].second, lazy[i].second);
            lazy[rchild(i)].first = min(lazy[rchild(i)].first, lazy[i].second);
            lazy[rchild(i)].first = max(lazy[rchild(i)].first, lazy[i].first);
            lazy[rchild(i)].second = max(lazy[rchild(i)].second, lazy[i].first);
        }
        lazy[i].second = INF;
        lazy[i].first = -INF;
    }
    if(l>=ll && u<=uu) return seg[i];
    if(l>uu || u<ll) return INF;
    return min(query(l, mid(l, u), lchild(i), ll, uu), query(mid(l, u)+1, u, rchild(i), ll, uu));
}
int update(int l, int u, int i, int ll, int uu, int upval, int type){
    if(lazy[i].second != INF || lazy[i].first != -INF){
        seg[i] = min(seg[i], lazy[i].second);
        seg[i] = max(seg[i], lazy[i].first);
        if(l!=u){
            lazy[lchild(i)].second = min(lazy[lchild(i)].second, lazy[i].second);
            lazy[lchild(i)].first = min(lazy[lchild(i)].first, lazy[i].second);
            lazy[lchild(i)].first = max(lazy[lchild(i)].first, lazy[i].first);
            lazy[lchild(i)].second = max(lazy[lchild(i)].second, lazy[i].first);

            lazy[rchild(i)].second = min(lazy[rchild(i)].second, lazy[i].second);
            lazy[rchild(i)].first = min(lazy[rchild(i)].first, lazy[i].second);
            lazy[rchild(i)].first = max(lazy[rchild(i)].first, lazy[i].first);
            lazy[rchild(i)].second = max(lazy[rchild(i)].second, lazy[i].first);
        }
        lazy[i].second = INF;
        lazy[i].first = -INF;
    }
    if(l>=ll && u<=uu){
        if(type==1){
            lazy[i].first = max(lazy[i].first, upval);
        }
        else{
            lazy[i].second = min(lazy[i].second, upval);
        }
        if(lazy[i].second != INF || lazy[i].first != -INF){
            //cout<<l<<" "<<u<<" updating "<<lazy[i].first<<" "<<lazy[i].second<<"\n";
            seg[i] = min(seg[i], lazy[i].second);
            seg[i] = max(seg[i], lazy[i].first);
            if(l!=u){
                lazy[lchild(i)].second = min(lazy[lchild(i)].second, lazy[i].second);
                lazy[lchild(i)].first = min(lazy[lchild(i)].first, lazy[i].second);
                lazy[lchild(i)].first = max(lazy[lchild(i)].first, lazy[i].first);
                lazy[lchild(i)].second = max(lazy[lchild(i)].second, lazy[i].first);

                lazy[rchild(i)].second = min(lazy[rchild(i)].second, lazy[i].second);
                lazy[rchild(i)].first = min(lazy[rchild(i)].first, lazy[i].second);
                lazy[rchild(i)].first = max(lazy[rchild(i)].first, lazy[i].first);
                lazy[rchild(i)].second = max(lazy[rchild(i)].second, lazy[i].first);
            }
            lazy[i].second = INF;
            lazy[i].first = -INF;
        }
        return seg[i];
    }
    if(l>uu || u<ll) return seg[i];
    return seg[i] = min(update(l, mid(l, u), lchild(i), ll, uu, upval, type), update(mid(l, u)+1, u, rchild(i), ll, uu, upval, type));
}
void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalheight[]){
    build(0, n-1, 0);
    for(int i = 0;i<k;i++){
        update(0, n-1, 0, left[i], right[i], height[i], op[i]);
    }
    for(int i = 0;i<n;i++) finalheight[i] = query(0, n-1, 0, i, i);
}
/*signed main(){
    int n, k;
    cin>>n>>k;
    signed op[k], left[k], right[k], height[k];
    signed finalheight[n];
    for(int i =0 ;i<k;i++){
        cin>>op[i]>>left[i]>>right[i]>>height[i];
    }
    buildWall(n, k, op, left, right, height, finalheight);
    for(int i = 0;i<n;i++) cout<<finalheight[i]<<" ";
    cout<<"\n";
}*/
/*
 * 5
4
1 3 4 10
2 2 3 7
1 0 2 4
2 2 4 6
 */

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 14 ms 1408 KB Output is correct
5 Correct 13 ms 1408 KB Output is correct
6 Correct 11 ms 1408 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 186 ms 13944 KB Output is correct
3 Correct 260 ms 9080 KB Output is correct
4 Correct 777 ms 24672 KB Output is correct
5 Correct 382 ms 25592 KB Output is correct
6 Correct 345 ms 24056 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 14 ms 1328 KB Output is correct
5 Correct 11 ms 1408 KB Output is correct
6 Correct 12 ms 1408 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 178 ms 13944 KB Output is correct
9 Correct 266 ms 9080 KB Output is correct
10 Correct 763 ms 24608 KB Output is correct
11 Correct 377 ms 25688 KB Output is correct
12 Correct 341 ms 24060 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 182 ms 13968 KB Output is correct
15 Correct 47 ms 3064 KB Output is correct
16 Correct 796 ms 24824 KB Output is correct
17 Correct 366 ms 24184 KB Output is correct
18 Correct 358 ms 24312 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1408 KB Output is correct
5 Correct 11 ms 1408 KB Output is correct
6 Correct 13 ms 1408 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 178 ms 13944 KB Output is correct
9 Correct 272 ms 9024 KB Output is correct
10 Correct 760 ms 24568 KB Output is correct
11 Correct 373 ms 25592 KB Output is correct
12 Correct 357 ms 24056 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 178 ms 14072 KB Output is correct
15 Correct 48 ms 3064 KB Output is correct
16 Correct 786 ms 24888 KB Output is correct
17 Correct 373 ms 24184 KB Output is correct
18 Correct 381 ms 24188 KB Output is correct
19 Correct 1339 ms 135284 KB Output is correct
20 Correct 1317 ms 132776 KB Output is correct
21 Correct 1342 ms 135440 KB Output is correct
22 Correct 1336 ms 132688 KB Output is correct
23 Correct 1341 ms 132856 KB Output is correct
24 Correct 1337 ms 133116 KB Output is correct
25 Correct 1324 ms 132852 KB Output is correct
26 Correct 1353 ms 135292 KB Output is correct
27 Correct 1348 ms 135204 KB Output is correct
28 Correct 1372 ms 132684 KB Output is correct
29 Correct 1323 ms 132816 KB Output is correct
30 Correct 1279 ms 132728 KB Output is correct