oj.uz

Submission #762155

# Submission time Handle Problem Language Result Execution time Memory
762155 2023-06-21T01:58:45 Z fdnfksd Wall (IOI14_wall) C++14
100 / 100
 612 ms 162364 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
#define vi vector<int>
const ll maxN=5e5+10;
struct node
{
    ll x,y;
    node operator+(const node &o)
    {
        node ans;
        ans.x=max(x,o.x);
        ans.y=min(y,o.y);
        ans.x=min(ans.x,o.y);
        ans.y=max(ans.y,o.x);
        return ans;
    }
}st[4*maxN];
void update(ll pos,ll i,ll j,ll id,ll l,ll r)
{
    if(l==r)
    {
        st[id].x=i;
        st[id].y=j;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,i,j,id*2,l,mid);
    else update(pos,i,j,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
vector<int>in[maxN*4],out[maxN*4];
#define pb push_back
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    for(int i=0;i<k;i++)
    {
        in[left[i]].pb(i);
        out[right[i]+1].pb(i);
    }
    for(int i=0;i<k;i++)
    {
        update(i,-1e7,1e7,1,0,k-1);
    }
    for(int i=0;i<n;i++)
    {
        for(auto id:in[i])
        {
            if(op[id]==1)
            {
                update(id,height[id],1e7,1,0,k-1);
            }
            else update(id,0,height[id],1,0,k-1);
        }
        for(auto id:out[i])
        {
            update(id,-1e7,1e7,1,0,k-1);
        }
        node cc={0,0};
        cc=cc+st[1];
        finalHeight[i]=cc.x;
    }
}

/*signed main()
{
    int n;
  int k;

  int i, j;
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }
  buildWall(n, k, op, left, right, height, finalHeight);
  cout << '\n';
  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);

  return 0;
}*/

Compilation message

wall.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
wall.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94164 KB Output is correct
2 Correct 44 ms 94468 KB Output is correct
3 Correct 43 ms 94356 KB Output is correct
4 Correct 46 ms 94796 KB Output is correct
5 Correct 45 ms 94780 KB Output is correct
6 Correct 45 ms 94668 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94204 KB Output is correct
2 Correct 268 ms 116888 KB Output is correct
3 Correct 225 ms 107544 KB Output is correct
4 Correct 571 ms 122868 KB Output is correct
5 Correct 355 ms 121236 KB Output is correct
6 Correct 363 ms 120860 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94220 KB Output is correct
2 Correct 43 ms 94516 KB Output is correct
3 Correct 41 ms 94244 KB Output is correct
4 Correct 46 ms 94832 KB Output is correct
5 Correct 45 ms 94744 KB Output is correct
6 Correct 45 ms 94780 KB Output is correct
7 Correct 41 ms 94264 KB Output is correct
8 Correct 260 ms 120216 KB Output is correct
9 Correct 216 ms 108756 KB Output is correct
10 Correct 577 ms 129948 KB Output is correct
11 Correct 360 ms 128732 KB Output is correct
12 Correct 359 ms 126900 KB Output is correct
13 Correct 40 ms 94156 KB Output is correct
14 Correct 271 ms 120228 KB Output is correct
15 Correct 68 ms 96768 KB Output is correct
16 Correct 612 ms 130056 KB Output is correct
17 Correct 394 ms 127092 KB Output is correct
18 Correct 441 ms 126824 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94164 KB Output is correct
2 Correct 42 ms 94488 KB Output is correct
3 Correct 46 ms 94332 KB Output is correct
4 Correct 45 ms 94804 KB Output is correct
5 Correct 43 ms 94788 KB Output is correct
6 Correct 47 ms 94664 KB Output is correct
7 Correct 41 ms 94200 KB Output is correct
8 Correct 257 ms 120228 KB Output is correct
9 Correct 216 ms 108784 KB Output is correct
10 Correct 596 ms 129892 KB Output is correct
11 Correct 351 ms 128852 KB Output is correct
12 Correct 380 ms 126860 KB Output is correct
13 Correct 54 ms 94184 KB Output is correct
14 Correct 273 ms 120184 KB Output is correct
15 Correct 69 ms 96668 KB Output is correct
16 Correct 599 ms 130180 KB Output is correct
17 Correct 395 ms 127084 KB Output is correct
18 Correct 395 ms 126824 KB Output is correct
19 Correct 557 ms 162352 KB Output is correct
20 Correct 521 ms 159836 KB Output is correct
21 Correct 538 ms 162364 KB Output is correct
22 Correct 528 ms 159852 KB Output is correct
23 Correct 529 ms 159964 KB Output is correct
24 Correct 546 ms 159772 KB Output is correct
25 Correct 523 ms 159844 KB Output is correct
26 Correct 520 ms 162344 KB Output is correct
27 Correct 524 ms 162316 KB Output is correct
28 Correct 521 ms 159828 KB Output is correct
29 Correct 525 ms 159820 KB Output is correct
30 Correct 527 ms 159888 KB Output is correct