Submission #55988

#	Time	Username	Problem	Language	Result	Execution time	Memory
55988		imeimi2000	Sushi (JOI16_sushi)	C++17	100 / 100	6793 ms	70788 KiB

sushi

#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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80