oj.uz

Submission #471473

# Submission time Handle Problem Language Result Execution time Memory
471473 2021-09-09T13:04:39 Z MohamedFaresNebili Wall (IOI14_wall) C++14
100 / 100
 1194 ms 96288 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 min(up[v], down[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 28 ms 62924 KB Output is correct
2 Correct 30 ms 62944 KB Output is correct
3 Correct 29 ms 62900 KB Output is correct
4 Correct 36 ms 63132 KB Output is correct
5 Correct 34 ms 63116 KB Output is correct
6 Correct 39 ms 63048 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62856 KB Output is correct
2 Correct 188 ms 71364 KB Output is correct
3 Correct 211 ms 66948 KB Output is correct
4 Correct 542 ms 71888 KB Output is correct
5 Correct 367 ms 75368 KB Output is correct
6 Correct 377 ms 75372 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62812 KB Output is correct
2 Correct 29 ms 63024 KB Output is correct
3 Correct 33 ms 62892 KB Output is correct
4 Correct 35 ms 63072 KB Output is correct
5 Correct 34 ms 63172 KB Output is correct
6 Correct 34 ms 63064 KB Output is correct
7 Correct 28 ms 62788 KB Output is correct
8 Correct 241 ms 71208 KB Output is correct
9 Correct 206 ms 66740 KB Output is correct
10 Correct 537 ms 71772 KB Output is correct
11 Correct 402 ms 75324 KB Output is correct
12 Correct 418 ms 75360 KB Output is correct
13 Correct 27 ms 62916 KB Output is correct
14 Correct 191 ms 74436 KB Output is correct
15 Correct 59 ms 64040 KB Output is correct
16 Correct 540 ms 75116 KB Output is correct
17 Correct 380 ms 78572 KB Output is correct
18 Correct 365 ms 78532 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62796 KB Output is correct
2 Correct 31 ms 63052 KB Output is correct
3 Correct 29 ms 62972 KB Output is correct
4 Correct 36 ms 63048 KB Output is correct
5 Correct 34 ms 63052 KB Output is correct
6 Correct 34 ms 63120 KB Output is correct
7 Correct 32 ms 62824 KB Output is correct
8 Correct 188 ms 71212 KB Output is correct
9 Correct 215 ms 66700 KB Output is correct
10 Correct 540 ms 71776 KB Output is correct
11 Correct 370 ms 75372 KB Output is correct
12 Correct 377 ms 75376 KB Output is correct
13 Correct 29 ms 62800 KB Output is correct
14 Correct 191 ms 74308 KB Output is correct
15 Correct 59 ms 64064 KB Output is correct
16 Correct 528 ms 75256 KB Output is correct
17 Correct 375 ms 78572 KB Output is correct
18 Correct 383 ms 78544 KB Output is correct
19 Correct 1145 ms 95828 KB Output is correct
20 Correct 1162 ms 93424 KB Output is correct
21 Correct 1123 ms 96096 KB Output is correct
22 Correct 1132 ms 93688 KB Output is correct
23 Correct 1116 ms 93772 KB Output is correct
24 Correct 1112 ms 93620 KB Output is correct
25 Correct 1154 ms 93640 KB Output is correct
26 Correct 1134 ms 96232 KB Output is correct
27 Correct 1194 ms 96288 KB Output is correct
28 Correct 1121 ms 93752 KB Output is correct
29 Correct 1101 ms 93748 KB Output is correct
30 Correct 1163 ms 93740 KB Output is correct