Submission #1003992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003992		AdamGS	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	205 ms	25428 KiB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
ll T[LIM];
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  T[0]=1;
  rep(i, n) {
    cin >> T[i+1];
    ll x=(T[i+1]+T[i]-1)/T[i];
    T[i+1]=x*T[i];
  }
  vector<pair<pair<ll,ll>,ll>>V;
  ll akt=0;
  rep(i, n) {
    if(T[i+1]!=T[akt]) {
      V.pb({{akt, i}, T[akt]});
      akt=i+1;
    }
  }
  V.pb({{akt, n}, T[akt]});
  while(q--) {
    ll t, l, r;
    cin >> t >> l >> r;
    ll ans=0;
    for(auto i : V) {
      ll p=t-(t%i.nd);
      ll a=-i.st.nd+p, b=-i.st.st+p;
      a=max(a, l);
      b=min(b, r);
      ans+=max(b-a+1, 0ll);
    }
    cout << ans << '\n';
  }
}

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