oj.uz

Submission #295068

# Submission time Handle Problem Language Result Execution time Memory
295068 2020-09-09T13:04:18 Z arayi Wall (IOI14_wall) C++17
100 / 100
 1294 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define MP make_pair
#define ad push_back
#define fr first
#define sc second
using namespace std;

const int N = 2e6 + 30;
const int n1 = 1e5;
int nn;
vector <pair<int, int> > fp[N], fp1[N], ff[N], ff1[N];
bool col[N];
priority_queue <int> h[n1 + 20], h1[n1 + 20];
int t1[4 * n1];
void upd1(int q, int l = 0, int r = n1, int nd = 1)
{
    if(q > r || q < l) return;
    if(l == r)
    {
        if(h1[l].empty()) t1[nd] = 0;
        else t1[nd] = h1[l].top();
        return;
    }
    int mid = (l + r) / 2;
    upd1(q, l, mid, nd * 2);
    upd1(q, mid + 1, r, nd * 2 + 1);
    t1[nd] = max(t1[nd * 2], t1[nd * 2 + 1]);
}
int t[4 * n1];
void upd(int q, int l = 0, int r = n1, int nd = 1)
{
    if(q > r || q < l) return;
    if(l == r)
    {
        if(h[l].empty()) t[nd] = 0;
        else t[nd] = h[l].top();
        return;
    }
    int mid = (l + r) / 2;
    upd(q, l, mid, nd * 2);
    upd(q, mid + 1, r, nd * 2 + 1);
    t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
int qry(int l = 0, int r = n1, int nd = 1, int a = 0, int b = 0)
{
    if(l == r) return l;
    int mid = (l + r) / 2;
    if(max(a, t1[nd * 2]) < max(b, t[nd * 2 + 1])) return qry(mid + 1, r, nd * 2 + 1, max(a, t1[nd * 2]), b);
    else return qry(l, mid, nd * 2, a, max(b, t[nd * 2 + 1]));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  nn = n;
  for (int i = 0; i < k; i++)
  {
      if(op[i] == 1) fp[left[i]].ad(MP(height[i], i + 1)), ff[right[i] + 1].ad(MP(height[i], i + 1));
      else fp1[left[i]].ad(MP(height[i], i + 1)), ff1[right[i] + 1].ad(MP(height[i], i + 1));
  }
  for (int i = 0; i < nn; i++)
  {
      for(auto p : fp[i])
      {
          h[p.fr].push(p.sc);
          upd(p.fr);
      }
      for(auto p : fp1[i])
      {
          h1[p.fr].push(p.sc);
          upd1(p.fr);
      }
      for(auto p : ff[i])
      {
          col[p.sc] = 1;
          while(!h[p.fr].empty() && col[h[p.fr].top()]) h[p.fr].pop();
          upd(p.fr);
      }
      for(auto p : ff1[i])
      {
          col[p.sc] = 1;
          while(!h1[p.fr].empty() && col[h1[p.fr].top()]) h1[p.fr].pop();
          upd1(p.fr);
      }
      finalHeight[i] = qry();
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 194424 KB Output is correct
2 Correct 136 ms 196856 KB Output is correct
3 Correct 135 ms 196472 KB Output is correct
4 Correct 143 ms 197216 KB Output is correct
5 Correct 139 ms 195576 KB Output is correct
6 Correct 139 ms 195576 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 194544 KB Output is correct
2 Correct 586 ms 223944 KB Output is correct
3 Correct 504 ms 212728 KB Output is correct
4 Correct 1229 ms 235768 KB Output is correct
5 Correct 637 ms 228220 KB Output is correct
6 Correct 613 ms 226832 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 194424 KB Output is correct
2 Correct 139 ms 196984 KB Output is correct
3 Correct 136 ms 196472 KB Output is correct
4 Correct 143 ms 197240 KB Output is correct
5 Correct 141 ms 195576 KB Output is correct
6 Correct 141 ms 195576 KB Output is correct
7 Correct 134 ms 194680 KB Output is correct
8 Correct 582 ms 223948 KB Output is correct
9 Correct 502 ms 212472 KB Output is correct
10 Correct 1214 ms 235640 KB Output is correct
11 Correct 626 ms 228216 KB Output is correct
12 Correct 601 ms 226660 KB Output is correct
13 Correct 130 ms 194424 KB Output is correct
14 Correct 576 ms 224100 KB Output is correct
15 Correct 192 ms 199928 KB Output is correct
16 Correct 1249 ms 236664 KB Output is correct
17 Correct 614 ms 227000 KB Output is correct
18 Correct 611 ms 226960 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 194536 KB Output is correct
2 Correct 135 ms 196856 KB Output is correct
3 Correct 135 ms 196540 KB Output is correct
4 Correct 141 ms 197368 KB Output is correct
5 Correct 144 ms 195576 KB Output is correct
6 Correct 140 ms 195576 KB Output is correct
7 Correct 130 ms 194424 KB Output is correct
8 Correct 586 ms 224200 KB Output is correct
9 Correct 493 ms 212472 KB Output is correct
10 Correct 1186 ms 235768 KB Output is correct
11 Correct 634 ms 228328 KB Output is correct
12 Correct 597 ms 226624 KB Output is correct
13 Correct 131 ms 194536 KB Output is correct
14 Correct 581 ms 224256 KB Output is correct
15 Correct 193 ms 200056 KB Output is correct
16 Correct 1294 ms 236664 KB Output is correct
17 Correct 609 ms 227000 KB Output is correct
18 Correct 622 ms 226960 KB Output is correct
19 Correct 1002 ms 262144 KB Output is correct
20 Correct 995 ms 260400 KB Output is correct
21 Correct 1010 ms 262144 KB Output is correct
22 Correct 990 ms 260452 KB Output is correct
23 Correct 992 ms 260368 KB Output is correct
24 Correct 981 ms 260328 KB Output is correct
25 Correct 992 ms 260116 KB Output is correct
26 Correct 1002 ms 262144 KB Output is correct
27 Correct 996 ms 262144 KB Output is correct
28 Correct 984 ms 260296 KB Output is correct
29 Correct 987 ms 260324 KB Output is correct
30 Correct 990 ms 260428 KB Output is correct