Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <set>
- #include <map>
- #include <climits>
- #include <cstdlib>
- #include<time.h>
- #include<iomanip>
- using namespace std;
- const int N = 2e5 + 7;
- long long a[N], s[N],i,n,q,mx,summ,l,cnt,vic,add;
- struct query {
- int num;
- long long mx,sum, cnt;
- };
- bool comp1(query a, query b) {
- if (a.mx == b.mx) {
- return a.num < b.num;
- }
- return a.mx < b.mx;
- }
- bool comp2(query a, query b) {
- return a.num < b.num;
- }
- query Q[N];
- void solve() {
- mx = Q[0].mx;
- l = 0;
- summ = 0;
- cnt = 0;
- for (i = 0; i < n-1; i++) {
- add = (a[i + 1] - 1 - summ) / a[i];
- cnt += add;
- summ += add * a[i];
- if (summ == mx) {
- //cout << summ << " " << cnt << "\n";
- Q[l].sum = summ;
- Q[l].cnt = cnt;
- l++;
- mx = Q[l].mx;
- i--;
- if (l == q) {
- return;
- }
- }
- if (summ > mx) {
- if ((summ - mx) % a[i] == 0) {
- vic = (summ - mx) / a[i];
- }
- else {
- vic = (summ - mx) / a[i] + 1;
- }
- Q[l].sum = summ - vic * a[i];
- Q[l].cnt = cnt - vic;
- l++;
- mx = Q[l].mx;
- i--;
- if (l == q) {
- return;
- }
- }
- }
- while(l < q){
- if (summ < mx) {
- vic = (mx - summ) / a[n - 1];
- Q[l].cnt = cnt + vic;
- Q[l].sum = summ + vic * a[n - 1];
- l++;
- mx = Q[l].mx;
- }
- else {
- Q[l].cnt = cnt;
- Q[l].sum = summ;
- l++;
- mx = Q[l].mx;
- }
- }
- }
- int main() {
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n;
- for (i = 0; i < n; i++) {
- cin >> a[i];
- }
- cin >> q;
- for (int I = 0; I < q; I++) {
- cin >> Q[I].mx;
- Q[I].num = I;
- }
- sort(Q, Q + q,comp1);
- solve();
- sort(Q, Q + q, comp2);
- for (i = 0; i < q; i++) {
- cout << Q[i].sum << " " << Q[i].cnt << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement