oj.uz

Submission #315528

# Submission time Handle Problem Language Result Execution time Memory
315528 2020-10-23T03:40:57 Z qpwoeirut Wall (IOI14_wall) C++17
32 / 100
 1533 ms 98040 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int MN = 100005;

void chmn(int& a, const int b) {if (a>b) a=b;}
void chmx(int& a, const int b) {if (a<b) a=b;}

void solve_sub1(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    fill(finalHeight, finalHeight+N, 0);

    for (int i=0; i<K; ++i) {
        for (int j=left[i]; j<=right[i]; ++j) {
            if (op[i] == 1) {
                chmx(finalHeight[j], height[i]);
            } else {
                chmn(finalHeight[j], height[i]);
            }
        }
    }
}

multiset<int> add[MN][2], rem[MN][2];
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    if (N <= 10000 && K <= 5000) {
        solve_sub1(N, K, op, left, right, height, finalHeight);
        return;
    }
    for (int i=0; i<K; ++i) {
        if (op[i] == 1) {
            add[left[i]][0].insert(height[i]);
            add[right[i]][1].insert(height[i]);
        } else {
            rem[left[i]][0].insert(height[i]);
            rem[right[i]][1].insert(height[i]);
        }
    }

    multiset<int> cur;
    cur.insert(0);
    for (int i=0; i<N; ++i) {
        cur.insert(add[i][0].begin(), add[i][0].end());

        finalHeight[i] = *cur.rbegin();

        for (multiset<int>::iterator it=add[i][1].begin(); it!=add[i][1].end(); ++it) {
            cur.erase(cur.find(*it));
        }
    }
    //for (int i=0; i<N; ++i) cerr << finalHeight[i] << ' '; cerr << endl;

    assert(cur.size() == 1 && *cur.begin() == 0);
    cur.clear();
    cur.insert(1001001001);
    for (int i=0; i<N; ++i) {
        cur.insert(rem[i][0].begin(), rem[i][0].end());

        chmn(finalHeight[i], *cur.begin());

        for (multiset<int>::iterator it=rem[i][1].begin(); it!=rem[i][1].end(); ++it) {
            cur.erase(cur.find(*it));
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 36 ms 19328 KB Output is correct
5 Correct 34 ms 19328 KB Output is correct
6 Correct 35 ms 19328 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19072 KB Output is correct
2 Correct 1094 ms 92020 KB Output is correct
3 Correct 527 ms 46636 KB Output is correct
4 Correct 1533 ms 84316 KB Output is correct
5 Correct 472 ms 76960 KB Output is correct
6 Correct 456 ms 76868 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 35 ms 19328 KB Output is correct
5 Correct 33 ms 19328 KB Output is correct
6 Correct 34 ms 19360 KB Output is correct
7 Correct 13 ms 19072 KB Output is correct
8 Correct 997 ms 98040 KB Output is correct
9 Correct 543 ms 50424 KB Output is correct
10 Correct 1471 ms 93816 KB Output is correct
11 Correct 475 ms 86904 KB Output is correct
12 Correct 466 ms 85488 KB Output is correct
13 Correct 13 ms 19072 KB Output is correct
14 Incorrect 1116 ms 91744 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 37 ms 19328 KB Output is correct
5 Correct 34 ms 19328 KB Output is correct
6 Correct 34 ms 19328 KB Output is correct
7 Correct 15 ms 19072 KB Output is correct
8 Correct 1031 ms 97748 KB Output is correct
9 Correct 544 ms 50424 KB Output is correct
10 Correct 1489 ms 93612 KB Output is correct
11 Correct 472 ms 86904 KB Output is correct
12 Correct 462 ms 85240 KB Output is correct
13 Correct 13 ms 19072 KB Output is correct
14 Incorrect 1119 ms 91440 KB Output isn't correct
15 Halted 0 ms 0 KB -