oj.uz

Submission #1062863

# Submission time Handle Problem Language Result Execution time Memory
1062863 2024-08-17T11:20:28 Z uacoder123 Wall (IOI14_wall) C++14
100 / 100
 920 ms 161992 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#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) lli(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 <ii,lli> iii;
typedef pair <ii,ii> iiii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ii ra[4*2000001],lazy[4*2000001];
ii m(ii in,int s,int e)
{
  if(in.S<s)
    return mp(s,s);
  if(in.F>e)
    return mp(e,e);
  return mp(max(in.F,s),min(in.S,e));
}
void up(int node,int l,int r,int s,int e,int vs,int ve)
{
  if(r<s|l>e)
    return;
  ra[node]=m(ra[node],lazy[node].F,lazy[node].S);
    lazy[2*node+1]=m(lazy[2*node+1],lazy[node].F,lazy[node].S);
    lazy[2*node+2]=m(lazy[2*node+2],lazy[node].F,lazy[node].S);
  lazy[node]=mp(0,1000000);
  if(l>=s&&r<=e)
  {
    ra[node]=m(ra[node],vs,ve);
    lazy[2*node+1]=m(lazy[2*node+1],vs,ve);
    lazy[2*node+2]=m(lazy[2*node+2],vs,ve);
    return;
  }
  int m=(l+r)/2;
  up(2*node+1,l,m,s,e,vs,ve);
  up(2*node+2,m+1,r,s,e,vs,ve);
  ra[node].F=min(ra[2*node+1].F,ra[2*node+2].F);
  ra[node].S=max(ra[2*node+1].S,ra[2*node+2].S);
}
ii qu(int node,int l,int r,int i)
{
  ra[node]=m(ra[node],lazy[node].F,lazy[node].S);
  if(l!=r)
  {
    lazy[2*node+1]=m(lazy[2*node+1],lazy[node].F,lazy[node].S);
    lazy[2*node+2]=m(lazy[2*node+2],lazy[node].F,lazy[node].S);
  }
  lazy[node]=mp(0,1000000);
  if(l==r)
    return ra[node];
  int m=(l+r)/2;
  ii sa;
  if(i<=m)
    return qu(2*node+1,l,m,i);
  else
    return qu(2*node+2,m+1,r,i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  for(int i=0;i<4*n+1;++i)
  {
    lazy[i]=mp(0,1000000);
    ra[i]=mp(0,0);
  }
  for(int i=0;i<k;++i)
  {
    if(op[i]==1)
    up(0,0,n,left[i],right[i],height[i],1000000);
  else 
    up(0,0,n,left[i],right[i],0,height[i]);
  }
  for(int i=0;i<n;++i)
    finalHeight[i]=qu(0,0,n,i).F;
}

Compilation message

wall.cpp: In function 'void up(int, int, int, int, int, int, int)':
wall.cpp:31:7: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   31 |   if(r<s|l>e)
      |      ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 97 ms 8044 KB Output is correct
3 Correct 141 ms 5344 KB Output is correct
4 Correct 424 ms 21996 KB Output is correct
5 Correct 228 ms 22564 KB Output is correct
6 Correct 226 ms 21960 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 5 ms 1368 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 11836 KB Output is correct
9 Correct 146 ms 7760 KB Output is correct
10 Correct 422 ms 22080 KB Output is correct
11 Correct 221 ms 22804 KB Output is correct
12 Correct 214 ms 21924 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 93 ms 11788 KB Output is correct
15 Correct 30 ms 3164 KB Output is correct
16 Correct 589 ms 22284 KB Output is correct
17 Correct 227 ms 25144 KB Output is correct
18 Correct 224 ms 25168 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 5 ms 1344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 11888 KB Output is correct
9 Correct 145 ms 7704 KB Output is correct
10 Correct 425 ms 22200 KB Output is correct
11 Correct 221 ms 22820 KB Output is correct
12 Correct 216 ms 21844 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 92 ms 11844 KB Output is correct
15 Correct 30 ms 2904 KB Output is correct
16 Correct 548 ms 22352 KB Output is correct
17 Correct 237 ms 25172 KB Output is correct
18 Correct 220 ms 25168 KB Output is correct
19 Correct 826 ms 161876 KB Output is correct
20 Correct 851 ms 159316 KB Output is correct
21 Correct 815 ms 161992 KB Output is correct
22 Correct 786 ms 159556 KB Output is correct
23 Correct 822 ms 159412 KB Output is correct
24 Correct 817 ms 159552 KB Output is correct
25 Correct 816 ms 159676 KB Output is correct
26 Correct 881 ms 161956 KB Output is correct
27 Correct 920 ms 161856 KB Output is correct
28 Correct 804 ms 159316 KB Output is correct
29 Correct 808 ms 159388 KB Output is correct
30 Correct 823 ms 159312 KB Output is correct