oj.uz

Submission #250692

# Submission time Handle Problem Language Result Execution time Memory
250692 2020-07-18T17:46:13 Z uacoder123 Wall (IOI14_wall) C++14
100 / 100
 1363 ms 162244 KB 
            #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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 125564 KB Output is correct
2 Correct 65 ms 125584 KB Output is correct
3 Correct 79 ms 125560 KB Output is correct
4 Correct 75 ms 125688 KB Output is correct
5 Correct 73 ms 125664 KB Output is correct
6 Correct 73 ms 125688 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 125560 KB Output is correct
2 Correct 239 ms 133368 KB Output is correct
3 Correct 418 ms 128952 KB Output is correct
4 Correct 1277 ms 135416 KB Output is correct
5 Correct 425 ms 138104 KB Output is correct
6 Correct 396 ms 136704 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 125560 KB Output is correct
2 Correct 67 ms 125688 KB Output is correct
3 Correct 75 ms 125560 KB Output is correct
4 Correct 73 ms 125720 KB Output is correct
5 Correct 71 ms 125688 KB Output is correct
6 Correct 74 ms 125652 KB Output is correct
7 Correct 64 ms 125560 KB Output is correct
8 Correct 237 ms 133400 KB Output is correct
9 Correct 424 ms 128888 KB Output is correct
10 Correct 1184 ms 135416 KB Output is correct
11 Correct 418 ms 137852 KB Output is correct
12 Correct 411 ms 136696 KB Output is correct
13 Correct 65 ms 125560 KB Output is correct
14 Correct 258 ms 133368 KB Output is correct
15 Correct 128 ms 126200 KB Output is correct
16 Correct 1284 ms 136440 KB Output is correct
17 Correct 421 ms 135928 KB Output is correct
18 Correct 417 ms 135672 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 125560 KB Output is correct
2 Correct 67 ms 125620 KB Output is correct
3 Correct 66 ms 125560 KB Output is correct
4 Correct 74 ms 125664 KB Output is correct
5 Correct 70 ms 125688 KB Output is correct
6 Correct 71 ms 125688 KB Output is correct
7 Correct 63 ms 125560 KB Output is correct
8 Correct 233 ms 133368 KB Output is correct
9 Correct 422 ms 128888 KB Output is correct
10 Correct 1289 ms 135032 KB Output is correct
11 Correct 427 ms 137720 KB Output is correct
12 Correct 397 ms 136156 KB Output is correct
13 Correct 71 ms 125560 KB Output is correct
14 Correct 253 ms 133368 KB Output is correct
15 Correct 129 ms 126200 KB Output is correct
16 Correct 1232 ms 136220 KB Output is correct
17 Correct 414 ms 135524 KB Output is correct
18 Correct 416 ms 135800 KB Output is correct
19 Correct 1255 ms 161912 KB Output is correct
20 Correct 1247 ms 159480 KB Output is correct
21 Correct 1262 ms 162020 KB Output is correct
22 Correct 1268 ms 159436 KB Output is correct
23 Correct 1258 ms 159476 KB Output is correct
24 Correct 1286 ms 159592 KB Output is correct
25 Correct 1363 ms 159608 KB Output is correct
26 Correct 1330 ms 162160 KB Output is correct
27 Correct 1318 ms 162244 KB Output is correct
28 Correct 1240 ms 159480 KB Output is correct
29 Correct 1277 ms 159924 KB Output is correct
30 Correct 1278 ms 159608 KB Output is correct