oj.uz

Submission #55988

# Submission time Handle Problem Language Result Execution time Memory
55988 2018-07-09T09:17:07 Z imeimi2000 Sushi (JOI16_sushi) C++17
100 / 100
 6793 ms 70788 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int t = 700;
int n, q, g;
int v[400000];
priority_queue<int> mx[t];
priority_queue<int, vector<int>, greater<int>> pass[t];

void reconstruct(int x) {
    for (int i = x * t; i < (x + 1) * t && i < n; ++i) {
        pass[x].push(v[i]);
        v[i] = pass[x].top();
        pass[x].pop();
    }
    while (!pass[x].empty()) pass[x].pop();
}

void construct(int x) {
    while (!mx[x].empty()) mx[x].pop();
    for (int i = x * t; i < (x + 1) * t && i < n; ++i) {
        mx[x].push(v[i]);
    }
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v + i);
    }
    g = (n - 1) / t + 1;
    for (int i = 0; i < t; ++i) {
        for (int j = i * t; j < (i + 1) * t && j < n; ++j) {
            mx[i].push(v[j]);
        }
    }
    while (q--) {
        int s, e, p;
        scanf("%d%d%d", &s, &e, &p);
        --s; --e;
        int sg = s / t;
        int eg = e / t;
        reconstruct(sg);
        if (sg != eg) reconstruct(eg);
        if (sg == eg && s <= e) {
            for (int i = s; i <= e; ++i) {
                if (p < v[i]) swap(p, v[i]);
            }
        }
        else {
            for (int i = s; i < (sg + 1) * t && i < n; ++i) {
                if (p < v[i]) swap(p, v[i]);
            }
            for (int i = (sg + 1) % g; i != eg; i = (i + 1) % g) {
                pass[i].push(p);
                mx[i].push(p);
                p = mx[i].top();
                mx[i].pop();
            }
            for (int i = eg * t; i <= e; ++i) {
                if (p < v[i]) swap(p, v[i]);
            }
        }
        construct(sg);
        if (sg != eg) construct(eg);
        printf("%d\n", p);
    }
	return 0;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
telegraph.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", v + i);
         ~~~~~^~~~~~~~~~~~~
telegraph.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &s, &e, &p);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 376 KB Output is correct
2 Correct 225 ms 616 KB Output is correct
3 Correct 223 ms 704 KB Output is correct
4 Correct 220 ms 704 KB Output is correct
5 Correct 208 ms 704 KB Output is correct
6 Correct 213 ms 828 KB Output is correct
7 Correct 112 ms 828 KB Output is correct
8 Correct 107 ms 828 KB Output is correct
9 Correct 221 ms 828 KB Output is correct
10 Correct 249 ms 928 KB Output is correct
11 Correct 223 ms 928 KB Output is correct
12 Correct 232 ms 928 KB Output is correct
13 Correct 215 ms 928 KB Output is correct
14 Correct 136 ms 928 KB Output is correct
15 Correct 141 ms 928 KB Output is correct
16 Correct 120 ms 928 KB Output is correct
17 Correct 2 ms 928 KB Output is correct
18 Correct 2 ms 928 KB Output is correct
19 Correct 3 ms 928 KB Output is correct
20 Correct 2 ms 928 KB Output is correct
21 Correct 2 ms 928 KB Output is correct
22 Correct 3 ms 928 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5440 ms 70692 KB Output is correct
2 Correct 5414 ms 70692 KB Output is correct
3 Correct 2292 ms 70692 KB Output is correct
4 Correct 5614 ms 70692 KB Output is correct
5 Correct 4330 ms 70692 KB Output is correct
6 Correct 5691 ms 70692 KB Output is correct
7 Correct 5770 ms 70692 KB Output is correct
8 Correct 5887 ms 70788 KB Output is correct
9 Correct 2464 ms 70788 KB Output is correct
10 Correct 4820 ms 70788 KB Output is correct
11 Correct 2400 ms 70788 KB Output is correct
12 Correct 4708 ms 70788 KB Output is correct
13 Correct 5239 ms 70788 KB Output is correct
14 Correct 5905 ms 70788 KB Output is correct
15 Correct 2578 ms 70788 KB Output is correct
16 Correct 5334 ms 70788 KB Output is correct
17 Correct 4739 ms 70788 KB Output is correct
18 Correct 5917 ms 70788 KB Output is correct
19 Correct 5481 ms 70788 KB Output is correct
20 Correct 5933 ms 70788 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 376 KB Output is correct
2 Correct 225 ms 616 KB Output is correct
3 Correct 223 ms 704 KB Output is correct
4 Correct 220 ms 704 KB Output is correct
5 Correct 208 ms 704 KB Output is correct
6 Correct 213 ms 828 KB Output is correct
7 Correct 112 ms 828 KB Output is correct
8 Correct 107 ms 828 KB Output is correct
9 Correct 221 ms 828 KB Output is correct
10 Correct 249 ms 928 KB Output is correct
11 Correct 223 ms 928 KB Output is correct
12 Correct 232 ms 928 KB Output is correct
13 Correct 215 ms 928 KB Output is correct
14 Correct 136 ms 928 KB Output is correct
15 Correct 141 ms 928 KB Output is correct
16 Correct 120 ms 928 KB Output is correct
17 Correct 2 ms 928 KB Output is correct
18 Correct 2 ms 928 KB Output is correct
19 Correct 3 ms 928 KB Output is correct
20 Correct 2 ms 928 KB Output is correct
21 Correct 2 ms 928 KB Output is correct
22 Correct 3 ms 928 KB Output is correct
23 Correct 5440 ms 70692 KB Output is correct
24 Correct 5414 ms 70692 KB Output is correct
25 Correct 2292 ms 70692 KB Output is correct
26 Correct 5614 ms 70692 KB Output is correct
27 Correct 4330 ms 70692 KB Output is correct
28 Correct 5691 ms 70692 KB Output is correct
29 Correct 5770 ms 70692 KB Output is correct
30 Correct 5887 ms 70788 KB Output is correct
31 Correct 2464 ms 70788 KB Output is correct
32 Correct 4820 ms 70788 KB Output is correct
33 Correct 2400 ms 70788 KB Output is correct
34 Correct 4708 ms 70788 KB Output is correct
35 Correct 5239 ms 70788 KB Output is correct
36 Correct 5905 ms 70788 KB Output is correct
37 Correct 2578 ms 70788 KB Output is correct
38 Correct 5334 ms 70788 KB Output is correct
39 Correct 4739 ms 70788 KB Output is correct
40 Correct 5917 ms 70788 KB Output is correct
41 Correct 5481 ms 70788 KB Output is correct
42 Correct 5933 ms 70788 KB Output is correct
43 Correct 6120 ms 70788 KB Output is correct
44 Correct 6008 ms 70788 KB Output is correct
45 Correct 3615 ms 70788 KB Output is correct
46 Correct 5966 ms 70788 KB Output is correct
47 Correct 5725 ms 70788 KB Output is correct
48 Correct 6084 ms 70788 KB Output is correct
49 Correct 6464 ms 70788 KB Output is correct
50 Correct 6554 ms 70788 KB Output is correct
51 Correct 6793 ms 70788 KB Output is correct
52 Correct 5633 ms 70788 KB Output is correct
53 Correct 5567 ms 70788 KB Output is correct
54 Correct 6004 ms 70788 KB Output is correct
55 Correct 5943 ms 70788 KB Output is correct
56 Correct 5835 ms 70788 KB Output is correct
57 Correct 5801 ms 70788 KB Output is correct
58 Correct 5423 ms 70788 KB Output is correct
59 Correct 4861 ms 70788 KB Output is correct
60 Correct 5107 ms 70788 KB Output is correct
61 Correct 5349 ms 70788 KB Output is correct
62 Correct 5637 ms 70788 KB Output is correct
63 Correct 5526 ms 70788 KB Output is correct
64 Correct 2834 ms 70788 KB Output is correct
65 Correct 3541 ms 70788 KB Output is correct
66 Correct 3628 ms 70788 KB Output is correct
67 Correct 4878 ms 70788 KB Output is correct
68 Correct 5520 ms 70788 KB Output is correct
69 Correct 5320 ms 70788 KB Output is correct
70 Correct 5083 ms 70788 KB Output is correct