oj.uz

Submission #700577

# Submission time Handle Problem Language Result Execution time Memory
700577 2023-02-19T07:33:29 Z primenumber_zz Wall (IOI14_wall) C++14
8 / 100
 3000 ms 25116 KB 
#include <bits/stdc++.h>
using namespace std;

struct LazySegmentTree {
};

void buildWall(int n, int k, int op[], int left[],int right[],int height[], int finalHeight[]) {
    int MAX = 0;
    for(int i = 0; i < k; i++) {
        MAX = max(MAX,height[i]);
    }
    vector<int>l(n,0),r(n,MAX+1);
    vector<array<int,3>>tmp1,tmp2;
    for(int i = 0; i < k; i++) {
        if(op[i] == 1) {
            tmp1.push_back({height[i],1,i});
        }
        else {
            tmp2.push_back({height[i],1,i});
        }
    }
    while(true) {
        bool f = false;
        for(int i = 0; i < n; i++) {
            if(l[i]+1 < r[i]) f = true;
        }
        if(!f) break;
        vector<array<int,3>>q1 = tmp1,q2 = tmp2;
        for(int i = 0; i < n; i++) {
            if(l[i]+1 < r[i]) {
                int mid = (l[i]+r[i])/2;
                q1.push_back({mid,0,i});
                q2.push_back({mid,0,i});
            }
        }
        sort(q1.rbegin(),q1.rend());
        sort(q2.begin(),q2.end());
        vector<int>mx1(n),mx2(n);
        vector<int>s1(n,-1),s2(n,-1);
        {
            for(int i = 0; i < q1.size(); i++) {
                if(q1[i][1] == 1) {
                    int id = q1[i][2];
                    for(int j = left[id]; j <= right[id]; j++) {
                        s1[j] = max(s1[j],id);
                    }
                }
                else {
                    mx1[q1[i][2]] = s1[q1[i][2]];
                }
            }
        }
        {
            for(int i = 0; i < q2.size(); i++) {
                if(q2[i][1] == 1) {
                    int id = q2[i][2];
                    for(int j = left[id]; j <= right[id]; j++) {
                        s2[j] = max(s2[j],id);
                    }
                }
                else {
                    mx2[q2[i][2]] = s2[q2[i][2]];
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(l[i]+1 < r[i]) {
                int mid = (l[i]+r[i])/2;
                if(mx2[i] < mx1[i]) {
                    l[i] = mid;
                }
                else {
                    r[i] = mid;
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        finalHeight[i] = l[i];
    }
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:41:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int i = 0; i < q1.size(); i++) {
      |                            ~~^~~~~~~~~~~
wall.cpp:54:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int i = 0; i < q2.size(); i++) {
      |                            ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 9 ms 592 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 441 ms 1284 KB Output is correct
5 Correct 405 ms 1252 KB Output is correct
6 Correct 496 ms 1328 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1555 ms 24540 KB Output is correct
3 Execution timed out 3070 ms 11896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 8 ms 584 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 270 ms 1308 KB Output is correct
5 Correct 299 ms 1260 KB Output is correct
6 Correct 312 ms 1368 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1592 ms 25116 KB Output is correct
9 Execution timed out 3078 ms 11880 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 12 ms 592 KB Output is correct
3 Correct 15 ms 340 KB Output is correct
4 Correct 335 ms 1220 KB Output is correct
5 Correct 302 ms 1224 KB Output is correct
6 Correct 334 ms 1220 KB Output is correct
7 Correct 1 ms 260 KB Output is correct
8 Correct 1466 ms 25096 KB Output is correct
9 Execution timed out 3053 ms 11908 KB Time limit exceeded
10 Halted 0 ms 0 KB -