oj.uz

Submission #581442

# Submission time Handle Problem Language Result Execution time Memory
581442 2022-06-22T16:13:33 Z kamelfanger83 Wall (IOI14_wall) C++14
32 / 100
 771 ms 39796 KB 
#include <iostream>
#include <vector>
#include "wall.h"
#include <set>

using namespace std;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    if(n <= 10000 && k <= 5000){
        vector<int> heightl (n, 0);
        for(int update = 0; update < k; update++){
            for(int setter = left[update]; setter <= right[update]; setter++){
                if(op[update] == 1) heightl[setter] = max(heightl[setter], height[update]);
                else heightl[setter] = min(heightl[setter], height[update]);
            }
        }
        for(int finisher = 0; finisher < n; finisher++) finalHeight[finisher] = heightl[finisher];
    }
    else{
        vector<vector<int>> adds (n);
        vector<vector<int>> adde (n+1);
        vector<vector<int>> subs (n);
        vector<vector<int>> sube (n+1);
        for(int update = 0; update < k; update++){
            if(op[update] == 1){
                adds[left[update]].push_back(height[update]);
                adde[right[update]+1].push_back(height[update]);
            }
            else{
                subs[left[update]].push_back(height[update]);
                sube[right[update]+1].push_back(height[update]);
            }
        }

        vector<int> mad (n, 0);
        multiset<int, greater<>> b;
        for(int madder = 0; madder < n; madder++){
            for(int ins : adds[madder]) b.insert(ins);
            for(int rm : adde[madder]) b.erase(b.lower_bound(rm));
            if(b.size() > 0) mad[madder] = *(b.begin());
        }

        vector<int> msu (n, 10000001);
        multiset<int> s;
        for(int madder = 0; madder < n; madder++){
            for(int ins : subs[madder]) s.insert(ins);
            for(int rm : sube[madder]) s.erase(s.lower_bound(rm));
            if(s.size() > 0) msu[madder] = *(s.begin());
        }    
        for(int finisher = 0; finisher < n; finisher++) finalHeight[finisher] = min(mad[finisher], msu[finisher]);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 23 ms 444 KB Output is correct
5 Correct 19 ms 456 KB Output is correct
6 Correct 18 ms 448 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 437 ms 35584 KB Output is correct
3 Correct 196 ms 13128 KB Output is correct
4 Correct 771 ms 39748 KB Output is correct
5 Correct 268 ms 26960 KB Output is correct
6 Correct 240 ms 26940 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 20 ms 452 KB Output is correct
5 Correct 24 ms 484 KB Output is correct
6 Correct 20 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 447 ms 35504 KB Output is correct
9 Correct 203 ms 13076 KB Output is correct
10 Correct 758 ms 39796 KB Output is correct
11 Correct 294 ms 26928 KB Output is correct
12 Correct 292 ms 27096 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 448 ms 35492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 18 ms 452 KB Output is correct
5 Correct 20 ms 448 KB Output is correct
6 Correct 20 ms 452 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 434 ms 35592 KB Output is correct
9 Correct 203 ms 13092 KB Output is correct
10 Correct 724 ms 39744 KB Output is correct
11 Correct 267 ms 26980 KB Output is correct
12 Correct 238 ms 26988 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 455 ms 35428 KB Output isn't correct
15 Halted 0 ms 0 KB -