Submission #242330

#	Time	Username	Problem	Language	Result	Execution time	Memory
242330		lyc	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	19 / 100	325 ms	22844 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 5e5+5;
const int mxQ = 5e5+5;
const int mxT = 1e9;

int N, Q, D[mxN], P[mxN], ans[mxQ];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    FOR(i,1,N){
        cin >> D[i];
        P[i] = -i;
    }
    P[0] = 0;

    if (N > 1000) {
        FOR(i,1,Q){
            int T, L, R; cin >> T >> L >> R;
            cout << max(0, min(T,R) - max(T-N,L) + 1) << '\n';
        }
    } else {
        vector<tuple<int,int,int,int>> qu;
        FOR(i,1,Q){
            int T, L, R; cin >> T >> L >> R;
            qu.emplace_back(T,L,R,i);
        }
        sort(ALL(qu));
        for (auto& [T,L,R,i] : qu) {
            while (P[0] < T) {
                ++P[0];
                FOR(j,1,N){
                    if (P[j-1]-P[j] > D[j]) P[j] = P[j-1]-1;
                }
            }
            ans[i] = 0;
            FOR(j,0,N) if (L <= P[j] && P[j] <= R) ++ans[i];
        }

        FOR(i,1,Q){
            cout << ans[i] << '\n';
        }
    }
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:41:20: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for (auto& [T,L,R,i] : qu) {
                    ^

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81