Submission #597481

#	Time	Username	Problem	Language	Result	Execution time	Memory
597481		79brue	Sushi (JOI16_sushi)	C++17	100 / 100	9061 ms	95628 KiB

sushi

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int LIM = 500;

int n, q;
int arr[400002];
priority_queue<int> exist[2000]; /// 존재하는 수들의 multiset
priority_queue<int, vector<int>, greater<int> > add[2000]; /// 추가될 수들의 multiset

void remakePQ(int g){
    int s = g*LIM, e = min(g*LIM+LIM-1, n-1);
    while(!add[g].empty()) add[g].pop();
    while(!exist[g].empty()) exist[g].pop();
    for(int i=s; i<=e; i++) exist[g].push(arr[i]);
}

void resolve(int g){
    int s = g*LIM, e = min(g*LIM+LIM-1, n-1);
    for(int i=s; i<=e; i++){
        add[g].push(arr[i]);
        arr[i] = add[g].top();
        add[g].pop();
    }
    remakePQ(g);
}

int solve(int s, int e, int v){ /// s에서 e 사이에 v를 추가한다
    int sg = s/LIM, eg = e/LIM;
    if(sg == eg){
        resolve(sg);
        for(int i=s; i<=e; i++){
            if(arr[i] > v) swap(arr[i], v);
        }
        remakePQ(sg);
        return v;
    }

    { /// sg 처리
        resolve(sg);
        for(int i=s; i<(sg+1)*LIM; i++) if(arr[i] > v) swap(arr[i], v);
        remakePQ(sg);
    }
    for(int i=sg+1; i<eg; i++){
        add[i].push(v);
        exist[i].push(v);
        v = exist[i].top();
        exist[i].pop();
    }
    { /// sg 처리
        resolve(eg);
        for(int i=eg*LIM; i<=e; i++) if(arr[i] > v) swap(arr[i], v);
        remakePQ(eg);
    }
    return v;
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }
    for(int i=0; (i+1)*LIM<n; i++) remakePQ(i);
    for(int i=1; i<=q; i++){
        int s, e, v;
        scanf("%d %d %d", &s, &e, &v);
        s--, e--;
        if(s<=e) printf("%d\n", solve(s, e, v));
        else printf("%d\n", solve(0, e, solve(s, n-1, v)));
    }
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d %d", &s, &e, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80