oj.uz

Submission #250682

# Submission time Handle Problem Language Result Execution time Memory
250682 2020-07-18T17:33:08 Z uacoder123 Wall (IOI14_wall) C++14
61 / 100
 1515 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];
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,int &t,int &s,int &e,int &h)
{
  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,t,s,e,h);
  up(2*node+2,m+1,r,t,s,e,h);
  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,int &s,int &e)
{
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,s,e),q2=qu(2*node+2,m+1,r,s,e);
  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)
  {
    up(0,0,n-1,op[i],left[i],right[i],height[i]);
  }
  for(int i=0;i<n;++i)
  {
    finalHeight[i]=(qu(0,0,n-1,i,i)).F;
    if(finalHeight[i]==8000001)
      finalHeight[i]=0;
  }
  return;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 250820 KB Output is correct
2 Correct 120 ms 251000 KB Output is correct
3 Correct 117 ms 250872 KB Output is correct
4 Correct 135 ms 251000 KB Output is correct
5 Correct 122 ms 251000 KB Output is correct
6 Correct 139 ms 251000 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 250836 KB Output is correct
2 Correct 303 ms 261368 KB Output is correct
3 Correct 512 ms 254516 KB Output is correct
4 Correct 1432 ms 262144 KB Output is correct
5 Correct 516 ms 262144 KB Output is correct
6 Correct 491 ms 262144 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 250872 KB Output is correct
2 Correct 121 ms 250872 KB Output is correct
3 Correct 118 ms 250872 KB Output is correct
4 Correct 131 ms 251000 KB Output is correct
5 Correct 122 ms 251128 KB Output is correct
6 Correct 124 ms 251000 KB Output is correct
7 Correct 116 ms 250744 KB Output is correct
8 Correct 296 ms 261380 KB Output is correct
9 Correct 512 ms 254364 KB Output is correct
10 Correct 1387 ms 262144 KB Output is correct
11 Correct 522 ms 262144 KB Output is correct
12 Correct 506 ms 262144 KB Output is correct
13 Correct 122 ms 250744 KB Output is correct
14 Correct 301 ms 261448 KB Output is correct
15 Correct 190 ms 251600 KB Output is correct
16 Correct 1505 ms 262144 KB Output is correct
17 Correct 543 ms 262144 KB Output is correct
18 Correct 529 ms 262144 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 250800 KB Output is correct
2 Correct 121 ms 250872 KB Output is correct
3 Correct 118 ms 250872 KB Output is correct
4 Correct 132 ms 251004 KB Output is correct
5 Correct 126 ms 251000 KB Output is correct
6 Correct 124 ms 251044 KB Output is correct
7 Correct 119 ms 250744 KB Output is correct
8 Correct 304 ms 260984 KB Output is correct
9 Correct 520 ms 254200 KB Output is correct
10 Correct 1394 ms 262144 KB Output is correct
11 Correct 535 ms 262144 KB Output is correct
12 Correct 513 ms 262144 KB Output is correct
13 Correct 119 ms 250744 KB Output is correct
14 Correct 305 ms 261112 KB Output is correct
15 Correct 186 ms 251384 KB Output is correct
16 Correct 1515 ms 262144 KB Output is correct
17 Correct 510 ms 262144 KB Output is correct
18 Correct 518 ms 262144 KB Output is correct
19 Runtime error 1029 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -