QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410450#8648. TowerRafi220 2ms3792kbC++141.7kb2024-05-14 01:00:552024-05-14 01:00:56

Judging History

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

  • [2024-05-14 01:00:56]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3792kb
  • [2024-05-14 01:00:55]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=2007;

ll l[N],r[N];
vector<pair<ll,int>>Q[N];
ll mn[2*N],mx[2*N];
ll X[N];
ll d;

bool inside(int l,int r,int x)
{
	return l+(x-l%d+d)%d<=r;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    ll a,b;
    cin>>n>>q>>d>>a>>b;
    vector<pair<ll,int>>V;
    for(int i=1;i<=n;i++)
    {
		cin>>l[i]>>r[i];
		if(r[i]+1>=d) V.pb({r[i]+1-d,i});
	}
    for(int i=1;i<=n+q;i++)
    {
		mn[i]=infl;
		mx[i]=-infl;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>X[i];
		V.pb({X[i],i+n});
	}
	sort(all(V));
	int j=0;
	for(auto [x,i]:V)
	{
		while(j<n&&x>r[j+1]) j++;
		if(j==n||x<l[j+1]) Q[j].pb({x,i});
	}
	r[0]=-1;
	for(int i=0;i<=n;i++)
	{
		if(i>0)
		{
			mn[i]++;
			mx[i]++;
		}
		//cout<<mn[i]<<" "<<mx[i]<<endl;
		for(int j=i;j<=n;j++)
		{
			if(inside(l[j],r[j],(r[i]+1)%d)) break;
			for(auto [x,k]:Q[j])
			{
				//cout<<i<<" "<<k<<" "<<l[j]+1<<" "<<x<<endl;
				if(inside(r[j]+1,x,(r[i]+1)%d))
				{
					mn[k]=min(mn[k],mn[i]+(r[j]+1-(r[i]+1)+d-1)/d);
					mx[k]=max(mx[k],mx[i]+(x-(r[i]+1))/d);
				}
			}
		}
	}
	for(int i=1;i<=q;i++)
	{
		if(mn[n+i]==infl) cout<<-1<<endl;
		else
		{
			//cout<<mn[n+i]<<" "<<mx[n+i]<<endl;
			ll w1=(X[i]-mn[n+i]*d)*a+b*mn[n+i];
			ll w2=(X[i]-mx[n+i]*d)*a+b*mx[n+i];
			cout<<min(w1,w2)<<endl;
		}
	}
    return 0;
}
/*
5 1
10 1 9
7 11
25 32
37 38
43 44
50 52
60
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

2000 200000
500 66309 387245
91 122
793 1029
1127 1131
1304 1611
2007 2039
2601 2701
2906 3052
3253 3263
3495 3609
4157 4225
4283 4283
4757 4766
4786 4847
4885 5086
5326 5342
5607 5750
5847 5877
6093 6230
6548 6793
7206 7308
7413 7419
7752 7780
8244 8410
8501 8515
9335 9447
9512 9514
9602 9906
10076...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #29:

score: 0
Wrong Answer
time: 2ms
memory: 3792kb

input:

1938 1960
999999 47694 9291
2883622 3085639
3674880 3745876
9982198101 9982517489
19960889157 19960925795
19962228551 19962276101
19964301694 19964730442
19964826417 19965369252
19965984922 19966442459
19968019821 19968213820
19968334967 19968392242
19968426638 19968840337
19969017519 19969109591
19...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 1st lines differ - expected: '2629532778036', found: '-1'

Subtask #3:

score: 0
Runtime Error

Test #44:

score: 0
Runtime Error

input:

198085 196577
999999 1 999999
562622 895604
1799586 1975565
2518299 2941986
4934097 5403130
5755102 5996130
6036200 6112534
6391882 6431514
6451793 6555786
6613625 6621089
7130933 7204522
7335426 7522555
7748545 7784568
8184979 8494887
9066856 9178094
9303615 9384897
9716200 9719420
11693951 1183563...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%