oj.uz

Submission #250689

# Submission time Handle Problem Language Result Execution time Memory
250689 2020-07-18T17:39:18 Z uacoder123 Wall (IOI14_wall) C++14
61 / 100
 1393 ms 262148 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 134 ms 250744 KB Output is correct
2 Correct 117 ms 251000 KB Output is correct
3 Correct 118 ms 250872 KB Output is correct
4 Correct 127 ms 251000 KB Output is correct
5 Correct 125 ms 251088 KB Output is correct
6 Correct 125 ms 251044 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 250744 KB Output is correct
2 Correct 344 ms 258808 KB Output is correct
3 Correct 537 ms 254200 KB Output is correct
4 Correct 1393 ms 262144 KB Output is correct
5 Correct 503 ms 262144 KB Output is correct
6 Correct 474 ms 262144 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 250744 KB Output is correct
2 Correct 130 ms 250872 KB Output is correct
3 Correct 123 ms 250872 KB Output is correct
4 Correct 140 ms 251000 KB Output is correct
5 Correct 121 ms 251000 KB Output is correct
6 Correct 131 ms 251000 KB Output is correct
7 Correct 114 ms 250872 KB Output is correct
8 Correct 308 ms 258808 KB Output is correct
9 Correct 512 ms 254252 KB Output is correct
10 Correct 1336 ms 262144 KB Output is correct
11 Correct 491 ms 262144 KB Output is correct
12 Correct 466 ms 262144 KB Output is correct
13 Correct 113 ms 250872 KB Output is correct
14 Correct 305 ms 258620 KB Output is correct
15 Correct 191 ms 251384 KB Output is correct
16 Correct 1363 ms 262144 KB Output is correct
17 Correct 492 ms 262144 KB Output is correct
18 Correct 490 ms 262144 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 250744 KB Output is correct
2 Correct 127 ms 250876 KB Output is correct
3 Correct 129 ms 250872 KB Output is correct
4 Correct 142 ms 251000 KB Output is correct
5 Correct 121 ms 250988 KB Output is correct
6 Correct 119 ms 251000 KB Output is correct
7 Correct 127 ms 250872 KB Output is correct
8 Correct 308 ms 258696 KB Output is correct
9 Correct 486 ms 254200 KB Output is correct
10 Correct 1380 ms 262144 KB Output is correct
11 Correct 593 ms 262144 KB Output is correct
12 Correct 477 ms 262144 KB Output is correct
13 Correct 115 ms 250744 KB Output is correct
14 Correct 296 ms 258680 KB Output is correct
15 Correct 183 ms 251512 KB Output is correct
16 Correct 1349 ms 262144 KB Output is correct
17 Correct 475 ms 262144 KB Output is correct
18 Correct 485 ms 262144 KB Output is correct
19 Runtime error 990 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -