oj.uz

Submission #479646

# Submission time Handle Problem Language Result Execution time Memory
479646 2021-10-12T14:41:08 Z Apiram Wall (IOI14_wall) C++14
100 / 100
 1077 ms 99340 KB 
#include <bits/stdc++.h>
#include "wall.h"
 
        using namespace std;
 
        using ll  = long long;
        using ld  = long double;
 
        using vl  = vector<long long>;
 
        #define mp make_pair
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define ub upper_bound
        #define all(x) (x).begin() , (x).end()
 
        const int N = 2*100005;
        const long long MOD = 1e9+7;
        const long double EPS = 0.000000001;
        const double PI = 3.14159265358979323846;
        const int nx[4]={1, -1, 0, 0}, ny[4]={0, 0, 1, -1};
 
        long long gcd(int a, int b) { return (b==0?a:gcd(b, a%b)); }
        long long lcm(int a, int b) { return  a*(b/gcd(a, b)); }
        long long fact(int a) { return (a==1?1:a*fact(a-1)); }
 
    int up[4*2000005], down[4*2000005]; bitset<4*2000005>add;
    void prop(int v, int l, int r) {
        down[v*2]=min(down[v*2], down[v]);
        down[v*2]=max(down[v*2], up[v]);
        up[v*2]=max(up[v*2], up[v]);
        up[v*2]=min(up[v*2], down[v]);
        down[v*2+1]=min(down[v*2+1], down[v]);
        down[v*2+1]=max(down[v*2+1], up[v]);
        up[v*2+1]=max(up[v*2+1], up[v]);
        up[v*2+1]=min(up[v*2+1], down[v]);
    }
    void update0(int v, int l, int r, int lo, int hi, int val, int op) {
        if(l>hi||r<lo) return;
        if(l>=lo&&r<=hi) {
                if(op==1) {
                    up[v]=max(up[v], val);
                    down[v]=max(down[v], val);
                }
                else if(op==2) {
                    up[v]=min(up[v], val);
                    down[v]=min(down[v], val);
                }
                return;
        }
      prop(v, l, r);
      down[v]=1000000007, up[v]=0;
        update0(v*2, l, (l+r)/2, lo, hi, val, op);
        update0(v*2+1, (l+r)/2+1, r, lo, hi, val, op);
    }
    int query(int v, int l, int r, int ind) {
            if(l==r) return up[v];
            int mid=(l+r)/2;
      prop(v, l, r);
      down[v]=1000000007, up[v]=0;
            if(ind<=mid) return query(v*2, l, mid, ind);
            else return query(v*2+1, mid+1, r, ind);
        }
 
        void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
            memset(up, 0, sizeof up);
            memset(down, 1000000007, sizeof down);
            for(int l=0;l<k;l++) {
                int t=op[l], a=left[l], b=right[l], w=height[l];
                update0(1, 0, n-1, a, b, w, t);
            }
            for(int l=0;l<n;l++) finalHeight[l]=query(1, 0, n-1, l);
            return;
        }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62924 KB Output is correct
2 Correct 30 ms 63012 KB Output is correct
3 Correct 27 ms 62916 KB Output is correct
4 Correct 32 ms 63180 KB Output is correct
5 Correct 34 ms 63200 KB Output is correct
6 Correct 34 ms 63180 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62924 KB Output is correct
2 Correct 196 ms 76468 KB Output is correct
3 Correct 182 ms 70064 KB Output is correct
4 Correct 559 ms 80872 KB Output is correct
5 Correct 329 ms 81936 KB Output is correct
6 Correct 376 ms 80364 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62924 KB Output is correct
2 Correct 29 ms 62996 KB Output is correct
3 Correct 28 ms 62868 KB Output is correct
4 Correct 30 ms 63072 KB Output is correct
5 Correct 30 ms 63052 KB Output is correct
6 Correct 34 ms 63132 KB Output is correct
7 Correct 25 ms 62808 KB Output is correct
8 Correct 183 ms 76668 KB Output is correct
9 Correct 199 ms 70008 KB Output is correct
10 Correct 491 ms 80836 KB Output is correct
11 Correct 337 ms 81988 KB Output is correct
12 Correct 350 ms 80456 KB Output is correct
13 Correct 25 ms 62864 KB Output is correct
14 Correct 175 ms 76456 KB Output is correct
15 Correct 52 ms 64104 KB Output is correct
16 Correct 498 ms 81204 KB Output is correct
17 Correct 324 ms 80580 KB Output is correct
18 Correct 377 ms 80544 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62924 KB Output is correct
2 Correct 27 ms 63064 KB Output is correct
3 Correct 27 ms 62924 KB Output is correct
4 Correct 31 ms 63088 KB Output is correct
5 Correct 34 ms 63092 KB Output is correct
6 Correct 31 ms 63148 KB Output is correct
7 Correct 25 ms 62788 KB Output is correct
8 Correct 195 ms 76456 KB Output is correct
9 Correct 184 ms 69988 KB Output is correct
10 Correct 502 ms 80868 KB Output is correct
11 Correct 327 ms 81988 KB Output is correct
12 Correct 319 ms 80388 KB Output is correct
13 Correct 27 ms 62924 KB Output is correct
14 Correct 175 ms 76488 KB Output is correct
15 Correct 61 ms 64020 KB Output is correct
16 Correct 491 ms 81216 KB Output is correct
17 Correct 344 ms 80580 KB Output is correct
18 Correct 322 ms 80676 KB Output is correct
19 Correct 1008 ms 99240 KB Output is correct
20 Correct 994 ms 96752 KB Output is correct
21 Correct 985 ms 99260 KB Output is correct
22 Correct 1000 ms 96840 KB Output is correct
23 Correct 1008 ms 96772 KB Output is correct
24 Correct 979 ms 96824 KB Output is correct
25 Correct 1008 ms 96784 KB Output is correct
26 Correct 1048 ms 99340 KB Output is correct
27 Correct 1077 ms 99252 KB Output is correct
28 Correct 1002 ms 96780 KB Output is correct
29 Correct 1055 ms 96800 KB Output is correct
30 Correct 1027 ms 96820 KB Output is correct