Submission #1040873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040873		Zero_OP	Fish 3 (JOI24_fish3)	C++14	100 / 100	259 ms	61524 KiB

Main

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX = 3e5 + 5;
 
#define mod __mod
#define div __div
 
int n, q, bad[MAX];
long long D, a[MAX], mod[MAX], div[MAX], handle[MAX], pref[MAX];
vector<pair<int, int>> queries[MAX];
 
long long st[MAX << 2], lazy[MAX << 2], answer[MAX];
bool applied[MAX << 2];
 
void apply(int id, int l, int r, long long val){
    st[id] = val * (r - l + 1);
    lazy[id] = val;
    applied[id] = true;
}
 
void pushDown(int id, int l, int r, int mid){
    if(applied[id]){
        apply(id << 1, l, mid, lazy[id]);
        apply(id << 1 | 1, mid + 1, r, lazy[id]);
        applied[id] = false;
        lazy[id] = 0;
    }
}
 
void update(int id, int l, int r, int u, int v, long long val){
    if(u <= l && r <= v){
        apply(id, l, r, val);
    }
    else{
        int mid = l + r >> 1;
        pushDown(id, l, r, mid);
        if(u <= mid) update(id << 1, l, mid, u, v, val);
        if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
}
 
long long query(int id, int l, int r, int u, int v){
    if(v < l || u > r) return 0;
    if(u <= l && r <= v) return st[id];
    int mid = l + r >> 1;
    pushDown(id, l, r, mid);
    return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> D;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        mod[i] = a[i] % D;
        div[i] = a[i] / D;
        if(mod[i - 1] > mod[i]) bad[i] = 1;
        bad[i] = bad[i - 1] + bad[i]; //mod[i - 1] > mod[i]
        handle[i] = div[i] - bad[i];
        pref[i] = pref[i - 1] + handle[i];
    }
 
    cin >> q;
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        queries[r].push_back({l, i});
    }
 
    stack<int> s;
    for(int i = 1; i <= n; ++i){
        while(!s.empty() && handle[s.top()] >= handle[i]){
            s.pop();
        }
        update(1, 1, n, (s.empty() ? 1 : s.top() + 1), i, handle[i]);
        s.push(i);
 
        for(auto [j, id] : queries[i]){
            long long minHandle = query(1, 1, n, j, j);
            if(bad[j] + minHandle < 0) answer[id] = -1;
            else answer[id] = pref[i] - pref[j - 1] - query(1, 1, n, j, i);
        }
    }
 
    for(int i = 0; i < q; ++i){
        cout << answer[i] << '\n';
    }
 
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void update(int, int, int, int, int, long long int)':
Main.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'long long int query(int, int, int, int, int)':
Main.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:83:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |         for(auto [j, id] : queries[i]){
      |                  ^

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36