oj.uz

Submission #986906

# Submission time Handle Problem Language Result Execution time Memory
986906 2024-05-21T14:26:23 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 500 ms 106704 KB 
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
const int N = 5e5 + 5;
const int M = 2e6 + 5;
pair<int,int> seg[N*4];
struct wall {
    int h, ty, ord;
};
pair<int,int> mer(pair<int,int> a, pair<int,int> b) {
        if(a.second < b.first) {
            return {b.first,b.first};
        }
        else if(a.first > b.second) {
            return {b.second,b.second};
        }
        else {
            return {max(a.first,b.first),min(a.second,b.second)};
        }

    return {0,INF};
}
void Build(int x, int l, int r) {
    if(l == r) {
        seg[x].first = 0;
        seg[x].second = INF;
    }
    else {
        int mid = (l+r)/2;
        Build(x*2,l,mid);
        Build(x*2+1,mid+1,r);
        seg[x].first = 0;
        seg[x].second = INF;
    }
}
void Update(int x, int l, int r, int pos, int ty, int val) {
    if(l == r) {
        if(val < 0) {
          //  cout << "aa" << endl;
            if(ty == 1) seg[x].first = 0;
            else seg[x].second = INF;
        }
        else {
          //  cout << "bb" << endl;
            if(ty == 1) seg[x].first = val;
            else seg[x].second = val;
        }
      //  cout << seg[x].first  << ' ' << seg[x].second << endl;
    }
    else {
        int mid = (l+r)/2;
        if(pos <= mid) Update(x*2,l,mid,pos,ty,val);
        else Update(x*2+1,mid+1,r,pos,ty,val);
        pair<int,int> pp = mer(seg[x*2],seg[x*2+1]);
    //    cout << l << ' ' << r << 'k' << endl;
      //  cout << pp.first << ' ' << pp.second << 'a' << endl;
        seg[x] = pp;
    }
}
vector<wall> v[M];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for(int i = 0; i < k; i++) {
        if(op[i] == 1) {
            wall cur;
            cur.h = height[i]+1;
            cur.ty = 1;
            cur.ord = i+1;
            v[left[i]].push_back(cur);
            cur.h *= -1;
            v[right[i]+1].push_back(cur);
        }
        else {
            wall cur;
            cur.h = height[i]+1;
            cur.ty = 2;
            cur.ord = i+1;
            v[left[i]].push_back(cur);
            cur.h *= -1;
            v[right[i]+1].push_back(cur);
        }
     }
     for(int i = 0; i < n; i++) finalHeight[i] = 1;
     Build(1,1,k+1);
     for(int i = 0; i < n; i++) {
        for(auto j : v[i]) {
           // cout << "JJJJJJJJJJJJJ" << endl;
           // cout << j.ord << ' ' << j.h << 'p' << endl;
            Update(1,1,k+1,j.ord,j.ty,j.h);
        }
        if(finalHeight[i] < seg[1].first) finalHeight[i] = seg[1].first;
        if(finalHeight[i] > seg[1].second) finalHeight[i] = seg[1].second;
     }
     for(int i = 0; i < n; i++) finalHeight[i]--;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 22 ms 47708 KB Output is correct
3 Correct 20 ms 47448 KB Output is correct
4 Correct 23 ms 47876 KB Output is correct
5 Correct 23 ms 47708 KB Output is correct
6 Correct 22 ms 47704 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47196 KB Output is correct
2 Correct 195 ms 75148 KB Output is correct
3 Correct 167 ms 62572 KB Output is correct
4 Correct 491 ms 83780 KB Output is correct
5 Correct 285 ms 81656 KB Output is correct
6 Correct 295 ms 80900 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 21 ms 47708 KB Output is correct
3 Correct 21 ms 47452 KB Output is correct
4 Correct 25 ms 47708 KB Output is correct
5 Correct 23 ms 47708 KB Output is correct
6 Correct 23 ms 47708 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct
8 Correct 203 ms 75404 KB Output is correct
9 Correct 157 ms 62556 KB Output is correct
10 Correct 452 ms 83936 KB Output is correct
11 Correct 286 ms 81524 KB Output is correct
12 Correct 285 ms 80848 KB Output is correct
13 Correct 21 ms 47192 KB Output is correct
14 Correct 204 ms 75308 KB Output is correct
15 Correct 43 ms 49708 KB Output is correct
16 Correct 465 ms 84048 KB Output is correct
17 Correct 334 ms 80408 KB Output is correct
18 Correct 309 ms 79956 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47196 KB Output is correct
2 Correct 24 ms 47736 KB Output is correct
3 Correct 21 ms 47452 KB Output is correct
4 Correct 24 ms 47708 KB Output is correct
5 Correct 24 ms 47708 KB Output is correct
6 Correct 23 ms 47704 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct
8 Correct 197 ms 75304 KB Output is correct
9 Correct 160 ms 62544 KB Output is correct
10 Correct 454 ms 83724 KB Output is correct
11 Correct 309 ms 81524 KB Output is correct
12 Correct 288 ms 80740 KB Output is correct
13 Correct 23 ms 47192 KB Output is correct
14 Correct 208 ms 75160 KB Output is correct
15 Correct 45 ms 49824 KB Output is correct
16 Correct 466 ms 84168 KB Output is correct
17 Correct 312 ms 80464 KB Output is correct
18 Correct 322 ms 79740 KB Output is correct
19 Correct 458 ms 106572 KB Output is correct
20 Correct 482 ms 104028 KB Output is correct
21 Correct 458 ms 106576 KB Output is correct
22 Correct 457 ms 104016 KB Output is correct
23 Correct 498 ms 104040 KB Output is correct
24 Correct 500 ms 104156 KB Output is correct
25 Correct 457 ms 104024 KB Output is correct
26 Correct 466 ms 106604 KB Output is correct
27 Correct 482 ms 106704 KB Output is correct
28 Correct 461 ms 104276 KB Output is correct
29 Correct 473 ms 104276 KB Output is correct
30 Correct 451 ms 104016 KB Output is correct