Submission #55987

#	Time	Username	Problem	Language	Result	Execution time	Memory
55987		imeimi2000	Sushi (JOI16_sushi)	C++17	0 / 100	12069 ms	67820 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;
struct pq {
    vector<int> x;
    pq() {}
    void push(int v) {
        x.push_back(v);
        for (int i = x.size() - 1; i > 0; ) {
            int p = (i - 1) >> 1;
            if (x[p] < x[i]) swap(x[p], x[i]);
            i = p;
        }
    }
    int top() const {
        return x[0];
    }
    bool empty() const {
        return x.empty();
    }
    void pop() {
        swap(x[0], x.back());
        x.pop_back();
        int i = 0;
        while (1) {
            int l = i << 1 | 1;
            if (x.size() <= l) break;
            int r = l + 1;
            if (x.size() <= r || x[r] < x[l]) {
                if (x[i] < x[l]) swap(x[i], x[l]);
                else break;
                i = l;
            }
            else {
                if (x[i] < x[r]) swap(x[i], x[r]);
                else break;
                i = r;
            }
        }
    }
    void clear() {
        x.clear();
    }
    void init(int arr[], int n) {
        x.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            x[i] = arr[i];
        }
        for (int i = n; i--; ) {
            int p = (i - 1) >> 1;
            if (x[i] < x[p]) continue;
            int j = i;
            while (1) {
                int l = i << 1 | 1;
                if (x.size() <= l) break;
                int r = l + 1;
                if (x.size() <= r || x[r] < x[l]) {
                    if (x[i] < x[l]) swap(x[i], x[l]);
                    else break;
                    i = l;
                }
                else {
                    if (x[i] < x[r]) swap(x[i], x[r]);
                    else break;
                    i = r;
                }
            }
        }
    }
};

int n, q, g;
int v[400000];
pq mx[t];
pq 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();
    }
    pass[x].clear();
}

void construct(int x) {
    mx[x].init(v + x * t, max(min(t, n - x * t), 0));
}

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) {
        construct(i);
    }
    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 member function 'void pq::pop()':
telegraph.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (x.size() <= l) break;
                 ~~~~~~~~~^~~~
telegraph.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (x.size() <= r || x[r] < x[l]) {
                 ~~~~~~~~~^~~~
telegraph.cpp: In member function 'void pq::init(int*, int)':
telegraph.cpp:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (x.size() <= l) break;
                     ~~~~~~~~~^~~~
telegraph.cpp:75:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (x.size() <= r || x[r] < x[l]) {
                     ~~~~~~~~~^~~~
telegraph.cpp:70:17: warning: unused variable 'j' [-Wunused-variable]
             int j = i;
                 ^
telegraph.cpp: In function 'int main()':
telegraph.cpp:109: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:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", v + i);
         ~~~~~^~~~~~~~~~~~~
telegraph.cpp:119: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: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80