Submission #250692

#	Time	Username	Problem	Language	Result	Execution time	Memory
250692		uacoder123	Wall (IOI14_wall)	C++14	100 / 100	1363 ms	162244 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 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,0))
                    return(n);
                  else if(n==mp(8000001,0))
                    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,0))
                  {
                    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;
                  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,0))
                  {
                    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:17: warning: control reaches end of non-void function [-Wreturn-type]
                 }
                 ^

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