Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, m, q, i, pozmax, pozmin, rezultat;
- long long sum[200002];
- struct valori
- {
- int original, suma;
- }v[100001];
- struct pozitii
- {
- int a, b, c, d;
- } poz[100001];
- int cautmax(int st, int dr, int x)
- {
- if (st > dr) return -1;
- else
- {
- int mij = (st + dr) / 2;
- if (x > v[dr].original) {
- return dr;
- }
- if (x < v[st].original) {
- return st - 1;
- }
- if (x < v[mij].original)
- return cautmax(st, mij - 1, x);
- else
- return cautmax(mij + 1, dr, x);
- }
- }
- int cautmin(int st, int dr, int x)
- {
- int mij = (st + dr) / 2;
- if (x == v[mij].original) {
- return x;
- }
- if (x > v[dr].original) {
- return dr + 1;
- }
- if (x < v[st].original) {
- return st;
- }
- if (x < v[mij].original)
- return cautmax(st, mij - 1, x);
- else
- return cautmax(mij + 1, dr, x);
- }
- void citire()
- {
- cin >> n >> m;
- for (i = 1; i <= n; ++i)
- {
- cin >> v[i].original;
- }
- cin >> q;
- for (i = 1; i <= q; i++)
- cin >> poz[i].a >> poz[i].b >> poz[i].c >> poz[i].d;
- }
- int main()
- {
- citire();
- v[1].suma = v[1].original;
- for (i = 2; i <= n; i++)
- {
- v[i].suma = v[i - 1].original + v[i].original;
- }
- for (i = 1; i <= q; ++i)
- {
- pozmin = cautmin(poz[i].a, poz[i].c, poz[i].b);
- pozmax = cautmax(pozmin, poz[i].c, poz[i].d);
- rezultat = v[pozmax].suma - v[pozmin - 1].suma - poz[i].b * (pozmax - pozmin + 1) + (poz[i].c - pozmax) * (poz[i].d - poz[i].b);
- cout << rezultat << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement