제출 #595755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595755		Cross_Ratio	Sushi (JOI16_sushi)	C++14	100 / 100	4120 ms	14712 KiB

sushi

#include <bits/stdc++.h>
using namespace std;
int A[400005];
int ans[400005];
int S[400005];
int T[400005];
int P[400005];
int SQ = 635;
vector<int> idx;
int id(int n) {
    return lower_bound(idx.begin(),idx.end(),n) - idx.begin();
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, Q;
    cin >> N >> Q;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    int pt = 1;
    for(j=1;j<=Q;j++) {
        cin >> S[j] >> T[j] >> P[j];
        S[j]--;
        T[j] %= N;
        if(j%SQ==0 || j == Q) {
            //cout << pt << " to " << j << '\n';
            idx.clear();
            for(i=pt;i<=j;i++) {
                idx.push_back(S[i]);
                idx.push_back(T[i]);
            }
            sort(idx.begin(),idx.end());
            idx.erase(unique(idx.begin(),idx.end()),idx.end());
            vector<priority_queue<int>> PQ;
            PQ.resize(idx.size());
            for(i=0;i+1<idx.size();i++) {
                for(int m = idx[i]; m < idx[i+1]; m++) {
                    PQ[i].push(A[m]);
                }
            }
            for(int m = idx[idx.size()-1];m<N;m++) {
                PQ[idx.size()-1].push(A[m]);
            }
            for(int m = 0; m < idx[0]; m++) {
                PQ[idx.size()-1].push(A[m]);
            }
            //cout <<"PQ init\n";
            vector<priority_queue<int,vector<int>,greater<int>>> Push;
            Push.resize(idx.size());
            for(i=pt;i<=j;i++) {
                int s = id(S[i]);
                int t = id(T[i]);
                int ans = P[i];
                if(s<t) {
                    for(int m = s; m < t; m++) {
                        Push[m].push(ans);
                        PQ[m].push(ans);
                        ans = PQ[m].top();
                        PQ[m].pop();
                    }
                }
                else {
                    for(int m = s; m < idx.size(); m++) {
                        Push[m].push(ans);
                        PQ[m].push(ans);
                        ans = PQ[m].top();
                        PQ[m].pop();
                    }
                    for(int m = 0; m < t; m++) {
                        Push[m].push(ans);
                        PQ[m].push(ans);
                        ans = PQ[m].top();
                        PQ[m].pop();
                    }
                }
                cout << ans << '\n';
            }
            for(i=0;i+1<idx.size();i++) {
                for(int m = idx[i]; m < idx[i+1]; m++) {
                    Push[i].push(A[m]);
                    A[m] = Push[i].top();
                    Push[i].pop();
                }
            }
            for(int m = idx[idx.size()-1];m<N;m++) {
                Push[idx.size()-1].push(A[m]);
                A[m] = Push[idx.size()-1].top();
                Push[idx.size()-1].pop();
            }
            for(int m = 0; m <idx[0]; m++) {
                Push[idx.size()-1].push(A[m]);
                A[m] = Push[idx.size()-1].top();
                Push[idx.size()-1].pop();
            }
            pt = j + 1;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

sushi.cpp: In function 'int main()':
sushi.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(i=0;i+1<idx.size();i++) {
      |                     ~~~^~~~~~~~~~~
sushi.cpp:64:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                     for(int m = s; m < idx.size(); m++) {
      |                                    ~~^~~~~~~~~~~~
sushi.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(i=0;i+1<idx.size();i++) {
      |                     ~~~^~~~~~~~~~~

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