oj.uz

Submission #986903

# Submission time Handle Problem Language Result Execution time Memory
986903 2024-05-21T14:23:37 Z Rifal Wall (IOI14_wall) C++14
61 / 100
 485 ms 57320 KB 
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
const int N = 5e5 + 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[N];
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 3 ms 12888 KB Output is correct
2 Correct 5 ms 13456 KB Output is correct
3 Correct 4 ms 12972 KB Output is correct
4 Correct 7 ms 13404 KB Output is correct
5 Correct 6 ms 13400 KB Output is correct
6 Correct 8 ms 13400 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 182 ms 45228 KB Output is correct
3 Correct 141 ms 30548 KB Output is correct
4 Correct 415 ms 57168 KB Output is correct
5 Correct 300 ms 55148 KB Output is correct
6 Correct 269 ms 53372 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 13148 KB Output is correct
3 Correct 4 ms 12944 KB Output is correct
4 Correct 7 ms 13364 KB Output is correct
5 Correct 6 ms 13404 KB Output is correct
6 Correct 6 ms 13408 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 181 ms 45224 KB Output is correct
9 Correct 139 ms 31684 KB Output is correct
10 Correct 404 ms 56520 KB Output is correct
11 Correct 281 ms 55252 KB Output is correct
12 Correct 298 ms 52632 KB Output is correct
13 Correct 3 ms 12888 KB Output is correct
14 Correct 198 ms 45348 KB Output is correct
15 Correct 25 ms 15192 KB Output is correct
16 Correct 485 ms 56660 KB Output is correct
17 Correct 300 ms 52692 KB Output is correct
18 Correct 334 ms 52100 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 5 ms 13060 KB Output is correct
3 Correct 4 ms 13088 KB Output is correct
4 Correct 7 ms 13176 KB Output is correct
5 Correct 6 ms 13404 KB Output is correct
6 Correct 6 ms 13400 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 184 ms 45528 KB Output is correct
9 Correct 140 ms 31572 KB Output is correct
10 Correct 462 ms 56660 KB Output is correct
11 Correct 267 ms 55404 KB Output is correct
12 Correct 287 ms 52624 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 190 ms 45200 KB Output is correct
15 Correct 26 ms 15308 KB Output is correct
16 Correct 462 ms 57320 KB Output is correct
17 Correct 292 ms 52816 KB Output is correct
18 Correct 292 ms 52052 KB Output is correct
19 Runtime error 139 ms 50000 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -