oj.uz

Submission #30483

# Submission time Handle Problem Language Result Execution time Memory
30483 2017-07-23T19:53:27 Z kavun Wall (IOI14_wall) C++14
100 / 100
 909 ms 50428 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
const int rgt = (1 << 21);
const int sz = (1<<22)+5;

int u[sz], d[sz];

void combine(int id, int down, int up)
{
  d[id] = min(d[id],down);
  d[id] = max(d[id],up);
  u[id] = max(u[id],up);
  u[id] = min(u[id],down);
}

void process(int id, char mode, int h)
{
  if(mode == 'u')
    {
      d[id] = max(d[id],h);
      u[id] = max(u[id],h);
    }
  else
    {
      d[id] = min(d[id],h);
      u[id] = min(u[id],h);
    }
}


void update(int id, int l, int r, int x, int y, int h, char mode)
{
  if(x > r || y < l)
    return;
  if(x <= l && y >= r)
    {
      process(id,mode,h);
      return;
    }
  combine(2*id,d[id],u[id]);
  combine(2*id+1,d[id],u[id]);
  d[id] = sz; u[id] = 0;

  int m = (l+r)/2;
  update(2*id,l,m,x,y,h,mode);
  update(2*id+1,m+1,r,x,y,h,mode);

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i = 0; i < k; i++)
    {
      char mode = op[i] == 1 ? 'u' : 'd';
      update(1,1,rgt,left[i]+1,right[i]+1,height[i],mode);
    }

  for(int i = 1; i < rgt-1; i++)
    combine(2*i,d[i],u[i]), combine(2*i+1,d[i],u[i]);
 

  for(int i = rgt; i <= rgt+n-1; i++)
    finalHeight[i-rgt] = min(d[i],u[i]);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 34788 KB Output is correct
2 Correct 29 ms 34924 KB Output is correct
3 Correct 23 ms 34788 KB Output is correct
4 Correct 19 ms 34924 KB Output is correct
5 Correct 26 ms 34924 KB Output is correct
6 Correct 19 ms 34924 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34788 KB Output is correct
2 Correct 446 ms 42612 KB Output is correct
3 Correct 279 ms 38184 KB Output is correct
4 Correct 706 ms 43004 KB Output is correct
5 Correct 429 ms 43004 KB Output is correct
6 Correct 439 ms 43004 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34788 KB Output is correct
2 Correct 23 ms 34924 KB Output is correct
3 Correct 3 ms 34788 KB Output is correct
4 Correct 23 ms 34924 KB Output is correct
5 Correct 13 ms 34924 KB Output is correct
6 Correct 16 ms 34924 KB Output is correct
7 Correct 3 ms 34788 KB Output is correct
8 Correct 443 ms 42612 KB Output is correct
9 Correct 229 ms 38184 KB Output is correct
10 Correct 629 ms 43004 KB Output is correct
11 Correct 413 ms 43004 KB Output is correct
12 Correct 393 ms 43004 KB Output is correct
13 Correct 16 ms 34788 KB Output is correct
14 Correct 486 ms 42612 KB Output is correct
15 Correct 49 ms 35416 KB Output is correct
16 Correct 639 ms 43004 KB Output is correct
17 Correct 393 ms 43004 KB Output is correct
18 Correct 396 ms 43004 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 34788 KB Output is correct
2 Correct 16 ms 34924 KB Output is correct
3 Correct 3 ms 34788 KB Output is correct
4 Correct 16 ms 34924 KB Output is correct
5 Correct 3 ms 34924 KB Output is correct
6 Correct 16 ms 34924 KB Output is correct
7 Correct 13 ms 34788 KB Output is correct
8 Correct 486 ms 42612 KB Output is correct
9 Correct 233 ms 38184 KB Output is correct
10 Correct 686 ms 43004 KB Output is correct
11 Correct 413 ms 43004 KB Output is correct
12 Correct 413 ms 43004 KB Output is correct
13 Correct 16 ms 34788 KB Output is correct
14 Correct 499 ms 42612 KB Output is correct
15 Correct 53 ms 35416 KB Output is correct
16 Correct 709 ms 43004 KB Output is correct
17 Correct 449 ms 43004 KB Output is correct
18 Correct 433 ms 43004 KB Output is correct
19 Correct 909 ms 50428 KB Output is correct
20 Correct 759 ms 50428 KB Output is correct
21 Correct 829 ms 50428 KB Output is correct
22 Correct 786 ms 50428 KB Output is correct
23 Correct 769 ms 50428 KB Output is correct
24 Correct 773 ms 50428 KB Output is correct
25 Correct 736 ms 50428 KB Output is correct
26 Correct 726 ms 50428 KB Output is correct
27 Correct 713 ms 50428 KB Output is correct
28 Correct 766 ms 50428 KB Output is correct
29 Correct 799 ms 50428 KB Output is correct
30 Correct 803 ms 50428 KB Output is correct