oj.uz

Submission #838493

# Submission time Handle Problem Language Result Execution time Memory
838493 2023-08-27T09:29:03 Z Andrey Wall (IOI14_wall) C++14
100 / 100
 537 ms 132224 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> seg(3000000,{0,INT_MAX});
vector<pair<pair<int,int>,int>> haha[2000000];

void upd(int l, int r, int x, int p, int y, int a) {
    if(l == r) {
        if(y == 0) {
            seg[x] = {a,seg[x].second};
        }
        else {
            seg[x] = {seg[x].first,a};
        }
        return;
    }
    int m = (l+r)/2;
    if(p <= m) {
        upd(l,m,x*2+1,p,y,a);
    }
    else {
        upd(m+1,r,x*2+2,p,y,a);
    }
    if(seg[x*2+2].first >= seg[x*2+1].second) {
        seg[x] = {min(seg[x*2+2].first,seg[x*2+2].second),min(seg[x*2+2].first,seg[x*2+2].second)};
    }
    else {
        seg[x] = {max(seg[x*2+1].first,seg[x*2+2].first),min(seg[x*2+1].second,seg[x*2+2].second)};
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++) {
        haha[left[i]].push_back({{i,op[i]-1},height[i]});
        int c = 0;
        if(op[i] == 2) {
            c = INT_MAX;
        }
        haha[right[i]+1].push_back({{i,op[i]-1},c});
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < haha[i].size(); j++) {
            upd(0,k-1,0,haha[i][j].first.first,haha[i][j].first.second,haha[i][j].second);
        }
        finalHeight[i] = min(seg[0].first,seg[0].second);
    }
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int j = 0; j < haha[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 70720 KB Output is correct
2 Correct 30 ms 71020 KB Output is correct
3 Correct 28 ms 70800 KB Output is correct
4 Correct 32 ms 71116 KB Output is correct
5 Correct 31 ms 71072 KB Output is correct
6 Correct 34 ms 71084 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70644 KB Output is correct
2 Correct 213 ms 90552 KB Output is correct
3 Correct 176 ms 81812 KB Output is correct
4 Correct 436 ms 99076 KB Output is correct
5 Correct 338 ms 96728 KB Output is correct
6 Correct 295 ms 95948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70740 KB Output is correct
2 Correct 29 ms 71060 KB Output is correct
3 Correct 31 ms 70824 KB Output is correct
4 Correct 33 ms 71032 KB Output is correct
5 Correct 37 ms 71068 KB Output is correct
6 Correct 32 ms 71048 KB Output is correct
7 Correct 28 ms 70740 KB Output is correct
8 Correct 211 ms 90360 KB Output is correct
9 Correct 160 ms 81812 KB Output is correct
10 Correct 487 ms 99004 KB Output is correct
11 Correct 301 ms 96848 KB Output is correct
12 Correct 306 ms 96180 KB Output is correct
13 Correct 27 ms 70708 KB Output is correct
14 Correct 218 ms 90396 KB Output is correct
15 Correct 52 ms 72652 KB Output is correct
16 Correct 537 ms 99300 KB Output is correct
17 Correct 319 ms 95664 KB Output is correct
18 Correct 333 ms 95124 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70740 KB Output is correct
2 Correct 30 ms 70916 KB Output is correct
3 Correct 30 ms 70832 KB Output is correct
4 Correct 33 ms 71048 KB Output is correct
5 Correct 37 ms 71128 KB Output is correct
6 Correct 35 ms 71124 KB Output is correct
7 Correct 29 ms 70740 KB Output is correct
8 Correct 205 ms 90368 KB Output is correct
9 Correct 159 ms 81768 KB Output is correct
10 Correct 442 ms 99100 KB Output is correct
11 Correct 301 ms 96800 KB Output is correct
12 Correct 306 ms 95916 KB Output is correct
13 Correct 28 ms 70740 KB Output is correct
14 Correct 221 ms 90456 KB Output is correct
15 Correct 52 ms 72660 KB Output is correct
16 Correct 508 ms 99268 KB Output is correct
17 Correct 315 ms 95612 KB Output is correct
18 Correct 322 ms 95120 KB Output is correct
19 Correct 456 ms 121740 KB Output is correct
20 Correct 459 ms 129712 KB Output is correct
21 Correct 467 ms 132188 KB Output is correct
22 Correct 484 ms 129724 KB Output is correct
23 Correct 461 ms 129696 KB Output is correct
24 Correct 495 ms 129748 KB Output is correct
25 Correct 463 ms 129752 KB Output is correct
26 Correct 519 ms 132216 KB Output is correct
27 Correct 478 ms 132224 KB Output is correct
28 Correct 506 ms 129712 KB Output is correct
29 Correct 453 ms 129732 KB Output is correct
30 Correct 461 ms 129628 KB Output is correct