Submission #1109147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109147		azberjibiou	Sushi (JOI16_sushi)	C++17	100 / 100	2271 ms	6868 KiB

sushi

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=400400;
const int mxQ=25050;
const int MOD=998244353;
const ll INF=1e18;
const int B=400;
int N, Q;
int A[mxN];
int s[mxQ], e[mxQ], h[mxQ];
int ans[mxQ];
priority_queue <int> pqA[2*B+5], pqH[2*B+5];
void input(){
    cin >> N >> Q;
    for(int i=1;i<=N;i++) cin >> A[i];
    for(int i=1;i<=Q;i++) cin >> s[i] >> e[i] >> h[i];
}
void add(int idx, int &nh){
    int maxi=pqA[idx].top();
    if(maxi<=nh) return;
    pqA[idx].pop();
    pqA[idx].push(nh);
    pqH[idx].push(-nh);
    nh=maxi;
}
void solv(int l, int r){
    vector <int> cr;
    cr.push_back(1); cr.push_back(N+1);
    for(int i=l;i<=r;i++) cr.push_back(s[i]), cr.push_back(e[i]+1);
    sort(all(cr));
    cr.erase(unique(all(cr)), cr.end());
    for(int i=0;i<cr.size()-1;i++){
        for(int j=cr[i];j<cr[i+1];j++) pqA[i].push(A[j]);
    }
    for(int i=l;i<=r;i++){
        int ns=s[i], ne=e[i]+1;
        ns=lower_bound(all(cr), ns)-cr.begin();
        ne=lower_bound(all(cr), ne)-cr.begin();
        if(ns<ne){
            int nh=h[i];
            for(int j=ns;j<ne;j++) add(j, nh);
            ans[i]=nh;
        }
        else{
            int nh=h[i];
            for(int j=ns;j+1<cr.size();j++) add(j, nh);
            for(int j=0;j<ne;j++) add(j, nh);
            ans[i]=nh;
        }
    }
    for(int i=0;i+1<cr.size();i++){
        for(int j=cr[i];j<cr[i+1];j++){
            if(pqH[i].empty()) break;
            int mini=-pqH[i].top();
            if(mini>=A[j]) continue;
            pqH[i].pop();
            pqH[i].push(-A[j]);
            A[j]=mini;
        }
    }

    for(int i=0;i<cr.size();i++) pqH[i]=priority_queue<int>(), pqA[i]=priority_queue<int>();
}
int main(){
    gibon
    input();
    for(int i=1;i<=Q;i+=B){
        solv(i, min(i+B-1, Q));
    }
    for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

sushi.cpp: In function 'void solv(int, int)':
sushi.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<cr.size()-1;i++){
      |                 ~^~~~~~~~~~~~
sushi.cpp:55:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int j=ns;j+1<cr.size();j++) add(j, nh);
      |                          ~~~^~~~~~~~~~
sushi.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i+1<cr.size();i++){
      |                 ~~~^~~~~~~~~~
sushi.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<cr.size();i++) pqH[i]=priority_queue<int>(), pqA[i]=priority_queue<int>();
      |                 ~^~~~~~~~~~

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