Submission #471472

#	Time	Username	Problem	Language	Result	Execution time	Memory
471472		MohamedFaresNebili	Wall (IOI14_wall)	C++14	8 / 100	680 ms	11268 KiB

wall

#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 st[6*2000005], lazy[6*2000005]; bitset<6*2000005>add;
		void prop(int v, int l, int r, int p) {
          	if(l==r||!add[v]) return;
			if(p==1) {
				lazy[v*2]=max(lazy[v*2], lazy[v]);
				st[v*2]=max(st[v*2], lazy[v*2]);
				lazy[v*2+1]=max(lazy[v*2+1], lazy[v]);
				st[v*2+1]=max(st[v*2+1], lazy[v*2+1]);
			}
			else if(p==2) {
				lazy[v*2]=min(lazy[v*2], lazy[v]);
				st[v*2]=min(st[v*2], lazy[v*2]);
				lazy[v*2+1]=min(lazy[v*2+1], lazy[v]);
				st[v*2+1]=min(st[v*2+1], lazy[v*2+1]);
			}
			add[v]=0; add[v*2]=add[v*2+1]=1;
		}
		void update0(int v, int l, int r, int lo, int hi, int val, int p) {
			prop(v, l, r, p);
			if(l>hi||r<lo) return;
			if(l>=lo&&r<=hi) {
				if(p==1) {
					lazy[v]=max(lazy[v], val);
					st[v]=max(st[v], lazy[v]);
					add[v]=1; prop(v, l, r, p);
				}
				else if(p==2) {
					lazy[v]=min(lazy[v], val);
					st[v]=min(st[v], lazy[v]);
					add[v]=1; prop(v, l, r, p);
				}
				return;
			}
			update0(v*2, l, (l+r)/2, lo, hi, val, p);
			update0(v*2+1, (l+r)/2+1, r, lo, hi, val, p);
		}
		int query(int v, int l, int r, int ind, int p) {
			prop(v, l, r, p);
			if(l==r) return st[v];
			int mid=(l+r)/2;
			if(ind<=mid) return query(v*2, l, mid, ind, p);
			else return query(v*2+1, mid+1, r, ind, p);
		}
 
        void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
			bool found=true; int cnt=0;
			for(int l=0;l<k;l++) {
				int prec=op[l]; int i=l;
				while(i<k&&op[i]==prec) prec=op[i++];
				l=i-1; cnt++;
			}
			if(cnt<=2) {
				int l=0;
				while(l<k&&op[l]==1) {
					int a=left[l], b=right[l], w=height[l];
					update0(1, 0, n-1, a, b, w, 1); l++;
				}
				for(int i=0;i<n;i++) query(1, 0, n-1, i, 1);
				while(l<k&&op[l]==2) {
					int a=left[l], b=right[l], w=height[l];
					update0(1, 0, n-1, a, b, w, 2); l++;
				}
				for(int i=0;i<n;i++) finalHeight[i]=query(1, 0, n-1, i, 2);
				return;
			}
			else {
				for(int l=0;l<k;l++) {
					int t=op[l], a=left[l], b=right[l], w=height[l];
					if(t==1) 
						for(int i=a;i<=b;i++) finalHeight[i]=max(finalHeight[i], w);
					else if(t==2)
						for(int i=a;i<=b;i++) finalHeight[i]=min(finalHeight[i], w);
				}
			}
            return;
        }

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:75:9: warning: unused variable 'found' [-Wunused-variable]
   75 |    bool found=true; int cnt=0;
      |         ^~~~~

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