oj.uz

Submission #242330

# Submission time Handle Problem Language Result Execution time Memory
242330 2020-06-27T08:55:29 Z lyc Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 325 ms 22844 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 7296 KB Output is correct
2 Correct 311 ms 22720 KB Output is correct
3 Correct 320 ms 22676 KB Output is correct
4 Correct 305 ms 22668 KB Output is correct
5 Correct 325 ms 22844 KB Output is correct
6 Correct 317 ms 22740 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 7296 KB Output is correct
2 Correct 311 ms 22720 KB Output is correct
3 Correct 320 ms 22676 KB Output is correct
4 Correct 305 ms 22668 KB Output is correct
5 Correct 325 ms 22844 KB Output is correct
6 Correct 317 ms 22740 KB Output is correct
7 Correct 10 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Incorrect 299 ms 22264 KB Output isn't correct
14 Halted 0 ms 0 KB -