9499 | 2024. 02. 22 12:19:28 | zeytonx | MI bróker (50 pont) | cpp17 | Időlimit túllépés 6/50 | 1.088s | 116456 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define pll pair<ll,ll>
#define vll vector<ll>
#define mll map<ll,ll>
#define fs first
#define sc second
const ll MOD = 1e9+7;
void solve()
{
ll n, q;
cin >> n >> q;
vector<ll> p(n);
map<ll, vll> lw, bg;
for(ll i = 0; i < n; i++)
{
cin >> p[i];
for(ll j = p[i]; j <= 500; j++)
lw[j].push_back(i);
for(ll j = 0; j <= p[i]; j++)
bg[j].push_back(i);
}
vector<pll> qr(q);
for(auto &i : qr)
cin >> i.fs >> i.sc;
for(auto i : qr)
{
ll ans = 0;
ll i1 = 0, i2 = 0;
while(true)
{
ans -= p[lw[i.fs][i1]];
i1++;
while(i2 < bg[i.sc].size() && lw[i.fs][i1-1] >= bg[i.sc][i2])
i2++;
if(i2 == bg[i.sc].size())
break;
ans += p[bg[i.sc][i2]];
i2++;
while(i1 < lw[i.fs].size() && lw[i.fs][i1] <= bg[i.sc][i2-1])
i1++;
if(i1 == lw[i.fs].size())
break;
}
cout << ans << "\n";
}
cout << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ll t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 6/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 2060 KiB | |||
2 | Időlimit túllépés | 0/0 | 1.08s | 49700 KiB | |||
3 | Futási hiba | 0/1 | 3ms | 2528 KiB | |||
4 | Futási hiba | 0/1 | 3ms | 2796 KiB | |||
5 | Elfogadva | 2/2 | 39ms | 14164 KiB | |||
6 | Elfogadva | 2/2 | 358ms | 108068 KiB | |||
7 | Elfogadva | 2/2 | 356ms | 108556 KiB | |||
8 | Futási hiba | 0/1 | 300ms | 113852 KiB | |||
9 | Futási hiba | 0/1 | 331ms | 114716 KiB | |||
10 | Időlimit túllépés | 0/2 | 1.057s | 59132 KiB | |||
11 | Futási hiba | 0/2 | 372ms | 116328 KiB | |||
12 | Futási hiba | 0/2 | 386ms | 116132 KiB | |||
13 | Futási hiba | 0/2 | 400ms | 116456 KiB | |||
14 | Futási hiba | 0/2 | 379ms | 115952 KiB | |||
15 | Időlimit túllépés | 0/3 | 1.069s | 57376 KiB | |||
16 | Időlimit túllépés | 0/3 | 1.049s | 57696 KiB | |||
17 | Időlimit túllépés | 0/3 | 1.07s | 58412 KiB | |||
18 | Időlimit túllépés | 0/3 | 1.05s | 57872 KiB | |||
19 | Időlimit túllépés | 0/3 | 1.062s | 58180 KiB | |||
20 | Időlimit túllépés | 0/3 | 1.065s | 58564 KiB | |||
21 | Időlimit túllépés | 0/3 | 1.06s | 59104 KiB | |||
22 | Időlimit túllépés | 0/3 | 1.078s | 59152 KiB | |||
23 | Időlimit túllépés | 0/3 | 1.067s | 58384 KiB | |||
24 | Időlimit túllépés | 0/3 | 1.088s | 58348 KiB |