QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267211#7622. Yet Another CoffeeuroskWA 0ms7548kbC++111.9kb2023-11-27 02:18:532023-11-27 02:18:53

Judging History

你现在查看的是最新测评结果

  • [2023-11-27 02:18:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7548kb
  • [2023-11-27 02:18:53]
  • 提交

answer

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;

#define maxn 200005
ll n,m;
pll a[maxn];
ll b[maxn];
ll c[maxn];
bool cmp(pll x,pll y){
    if(x.fi!=y.fi) return x.fi<y.fi;
    return x.sc>y.sc;
}
ll ans[maxn];
void tc(){
    cin >> n >> m;
    for(ll i = 1;i<=n;i++) ans[i] = llinf;
    for(ll i = 1;i<=n;i++) a[i].sc = i;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi;
    for(ll i = 1;i<=n+1;i++) c[i] = 0;
    for(ll i = 1;i<=m;i++){
        ll r,w; cin >> r >> w;
        c[r+1]-=w;
        c[1]+=w;
    }
    for(ll i = 1;i<=n;i++) c[i]+=c[i-1];
    for(ll i = 1;i<=n;i++) b[i] = a[i].fi - c[i];
    for(ll i = 1;i<=n;i++) b[i] = min(b[i],b[i-1]);
    sort(a+1,a+1+n,cmp);
    ll sum = 0;
    ll l = n+1;
    for(ll i = 1;i<=n;i++){
        l = min(l,a[i].sc);
        sum+=a[i].fi;
        ans[i] = min(ans[i],sum-c[l]);
        if(l>1) ans[i+1] = sum + b[l-1];
    }
    for(ll i = 1;i<=n;i++) cout<<ans[i]<< " ";
    cout<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	cin >> t;
	while(t--){
		tc();
	}
	return (0-0);
}
/**
2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
**/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7548kb

input:

5
10 14
17 37 59 65 53 73 68 177 160 111
10 177
5 193
2 30
3 63
2 339
3 263
5 178
2 190
9 23
10 328
10 200
9 8
3 391
6 230
12 9
152 306 86 88 324 59 18 14 42 260 304 55
3 50
2 170
1 252
7 811
1 713
7 215
10 201
4 926
8 319
19 20
182 74 180 201 326 243 195 31 170 263 284 233 48 166 272 281 179 116 31...

output:

-2596 -2559 -2506 -2447 -2382 -2314 -2241 -2130 -1970 -1793 
-506 -3491 -3473 -3431 -3376 -3317 -3231 -3143 -2883 -2579 -2273 -1949 
-4500 -6496 -6448 -6374 -6258 -6092 -5922 -5743 -5563 -5368 -5167 -4934 -4691 -4428 -4156 -3875 -3591 -3272 -2946 
232 -2987 -2572 -2140 -1707 -1238 -768 -274 243 1046...

result:

wrong answer 11th numbers differ - expected: '-3505', found: '-506'