Submission #250689

#	Time	Username	Problem	Language	Result	Execution time	Memory
250689		uacoder123	Wall (IOI14_wall)	C++14	61 / 100	1393 ms	262148 KiB

wall

    #include <stdio.h>
        #include <stdlib.h>
        #include <assert.h>
        #include "wall.h"
         
        #include <bits/stdc++.h>
        using namespace std;
        #define F first
        #define S second
        #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
        #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
        #define all(x) (x).begin(), (x).end()
        #define sz(x) int(x.size())
        #define mp(i,a) make_pair(i,a)
        #define pb(a) push_back(a)
        #define bit(x,b) (x&(1LL<<b))
         
        typedef long long int lli;
        typedef pair <lli,lli> ii;
        typedef pair <lli,ii> iii;
        typedef vector <lli> vi;
         
        ii segt[8000001],lazy[8000001];
        int s,e,t,h;
        ii imp(ii o,ii n)
        {
          if(o==mp(8000001*1LL,0*1LL))
            return(n);
          else if(n==mp(8000001*1LL,0*1LL))
            return(o);
          if(o.S<=n.F)
            return(mp(n.F,n.F));
          if(o.S>=n.F&&o.F<=n.F&&n.S>=o.S)
            return(mp(n.F,o.S));
          if(n.F>=o.F&&n.S<=o.S)
            return(n);
          if(o.F>=n.F&&o.S<=n.S)
            return(o);
          if(o.F>=n.F&&o.S>=n.S&&n.S>=o.F)
            return(mp(o.F,n.S));
          if(o.F>=n.S)
            return(mp(n.S,n.S));
        }
        void up(int node,int l,int r)
        {
          if(lazy[node]!=mp(8000001*1LL,0*1LL))
          {
            segt[node]=imp(segt[node],lazy[node]);
            lazy[2*node+1]=imp(lazy[2*node+1],lazy[node]);
            lazy[2*node+2]=imp(lazy[2*node+2],lazy[node]);
            lazy[node]=mp(8000001*1LL,0*1LL);
          }
          if(l>e||r<s)
            return;
          if(l>=s&&r<=e)
          {
            segt[node]=imp(segt[node],(t==1)?(mp(h,1000000)):(mp(0,h)));
            lazy[2*node+1]=imp(lazy[2*node+1],(t==1)?(mp(h,1000000)):(mp(0,h)));
            lazy[2*node+2]=imp(lazy[2*node+2],(t==1)?(mp(h,1000000)):(mp(0,h)));
            return;
          }
          int m=(l+r)/2;
          up(2*node+1,l,m);
          up(2*node+2,m+1,r);
          segt[node]=mp(min(segt[2*node+1].F,segt[2*node+2].F),max(segt[2*node+1].S,segt[2*node+2].S));
        }
        ii qu(int node,int l,int r)
        {
        if(lazy[node]!=mp(8000001*1LL,0*1LL))
          {
            segt[node]=imp(segt[node],lazy[node]);
            lazy[2*node+1]=imp(lazy[2*node+1],lazy[node]);
            lazy[2*node+2]=imp(lazy[2*node+2],lazy[node]);
            lazy[node]=mp(8000001,0);
          }
          if(l>e||r<s)
            return(mp(8000001,0));
          if(l>=s&&r<=e)
          {
            return(segt[node]);
          }
          int m=(l+r)/2;
          ii q1=qu(2*node+1,l,m),q2=qu(2*node+2,m+1,r);
          return(mp(min(q1.F,q2.F),max(q1.S,q2.S)));
        }
        void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
        {
          for(int i=0;i<8000001;++i)
          {
            lazy[i]=mp(8000001,0);
            segt[i]=mp(8000001,0);
          }
          for(int i=0;i<k;++i)
          {
            t=op[i];s=left[i],e=right[i],h=height[i];
            up(0,0,n-1);
          }
          for(int i=0;i<n;++i)
          {
            s=i;e=i;
            finalHeight[i]=(qu(0,0,n-1)).F;
            if(finalHeight[i]==8000001)
              finalHeight[i]=0;
          }
          return;
        }

Compilation message (stderr)

wall.cpp: In function 'ii imp(ii, ii)':
wall.cpp:43:9: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^

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