Submission #764210

#	Time	Username	Problem	Language	Result	Execution time	Memory
764210		minhcool	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	324 ms	25308 KiB

worst_reporter3

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 6e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, q, d[N];

vector<pair<int, ii>> v;// cycle, le, ri

#ifdef local
void process(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> d[i];
    int lst = d[1], lst2 = 1;
    v.pb({1, {0, 0}});
    for(int i = 2; i <= n; i++){
        if(d[i] > lst){
            v.pb({lst, {lst2, i - 1}});
            int temp = (d[i] + lst - 1) / lst;
            lst *= temp;
            lst2 = i;
        }
    }
    v.pb({lst, {lst2, n}});
    //cin >> q;
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
       // t--;
        int answer = 0;
        for(auto it : v){
            int temp = (t / it.fi) * it.fi;
            ii b = {-it.se.fi, -it.se.se};
            b.fi += temp, b.se += temp;
            swap(b.fi, b.se);
          //  cout << b.fi << " " << b.se << "\n";
            answer += max(0LL, min(r, b.se) - max(l, b.fi) + 1);
        }
        cout << answer << "\n";
    }
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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