#include <iostream> #include <vector> #include <algorithm> using namespace std; vector <unsigned long long> kwiaty; vector <pair <unsigned long long, unsigned long long> > dni; unsigned long long tab[500005]; unsigned long long dk[500005]; main() { ios_base::sync_with_stdio(0); int n, m; unsigned long long wynik; wynik=0; cin >> n >> m; unsigned long long q; kwiaty.push_back(0); for (int i=0; i<n; i++) { cin >> q; kwiaty.push_back(q); tab[i]=0; dk[i]=0; } tab[n]=dk[n]=0; unsigned long long x, y; for (int i=0; i<m; i++) { cin >> y >> x; dni.push_back(make_pair(x,y)); } sort (kwiaty.begin(), kwiaty.end()); unsigned long long p, k, s; for (int i=0; i<dni.size(); i++) { wynik=0; p=0; k=kwiaty.size()-2; s=(p+k)/2; while (!((kwiaty[s+1]*(dni[i].second-dk[s+1]))+tab[s+1]>dni[i].first && (kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first)) { if ((kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first) p=s; else k=s; s=(p+k)/2; if (p==k) break; if (p+1==k && !((kwiaty[s+1]*(dni[i].second-dk[s+1]))+tab[s+1]>dni[i].first && (kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first)) { s=kwiaty.size(); break; } } for (int j=s+1; j<kwiaty.size(); j++) { wynik+=(kwiaty[j]*(dni[i].second-dk[j]))+tab[j]-dni[i].first; tab[j]=dni[i].first; dk[j]=dni[i].second; } cout << wynik << endl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <iostream> #include <vector> #include <algorithm> using namespace std; vector <unsigned long long> kwiaty; vector <pair <unsigned long long, unsigned long long> > dni; unsigned long long tab[500005]; unsigned long long dk[500005]; main() { ios_base::sync_with_stdio(0); int n, m; unsigned long long wynik; wynik=0; cin >> n >> m; unsigned long long q; kwiaty.push_back(0); for (int i=0; i<n; i++) { cin >> q; kwiaty.push_back(q); tab[i]=0; dk[i]=0; } tab[n]=dk[n]=0; unsigned long long x, y; for (int i=0; i<m; i++) { cin >> y >> x; dni.push_back(make_pair(x,y)); } sort (kwiaty.begin(), kwiaty.end()); unsigned long long p, k, s; for (int i=0; i<dni.size(); i++) { wynik=0; p=0; k=kwiaty.size()-2; s=(p+k)/2; while (!((kwiaty[s+1]*(dni[i].second-dk[s+1]))+tab[s+1]>dni[i].first && (kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first)) { if ((kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first) p=s; else k=s; s=(p+k)/2; if (p==k) break; if (p+1==k && !((kwiaty[s+1]*(dni[i].second-dk[s+1]))+tab[s+1]>dni[i].first && (kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first)) { s=kwiaty.size(); break; } } for (int j=s+1; j<kwiaty.size(); j++) { wynik+=(kwiaty[j]*(dni[i].second-dk[j]))+tab[j]-dni[i].first; tab[j]=dni[i].first; dk[j]=dni[i].second; } cout << wynik << endl; } } |