QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#720292#9528. New Energy VehiclebulingRE 135ms15048kbC++144.2kb2024-11-07 11:40:042024-11-07 11:40:04

Judging History

This is the latest submission verdict.

  • [2024-11-07 11:40:04]
  • Judged
  • Verdict: RE
  • Time: 135ms
  • Memory: 15048kb
  • [2024-11-07 11:40:04]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define lll i << 1
#define rrr i << 1 | 1


//
 #define ll long long
 #define int long long
	#define ld long double
	#define rint register int
	#define inv inline void
	#define ini inline int
//    inline int read()
//    {
//        int sum=0;
//        char ch=getchar();
//        while(ch>'9'||ch<'0') ch=getchar();
//        while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
//        return sum;
//    }//读入优化
//	
//    
//    inline void print(int x){
//        if(!x){
//            putchar('0');
//            return;
//        }
//        int num[22],siz=0,px=x;
//        while(px){
//            siz++;
//            num[siz]=px%10;
//            px/=10;
//        }
//        while(siz){
//            putchar(num[siz]+'0');
//            siz--;
//        }
//    }   //快速输出
      __int128 read() {
	char arr[30];
	__int128 res = 0;
	scanf("%s", arr);
	for (int i = 1; i <= strlen(arr); i++) {
		res *= 10;
		res += arr[i]-'0';
	}
	return res;
}
void print (__int128 num) {
	if (num > 9) { print(num / 10); }
	putchar(num % 10 + '0');
}
      
      
      
    long long max(long long a,long long b)
    {
       return a>b?a:b;
    }
      
    long long min(long long a,long long b)
    {
       return a<b?a:b;
    }
     
      
    const int N=1e5+6;
    const int N2=1004; 
    int mod=1000000007;
    //int Mod=1e15+7;
    const int INF=2e17;
  	const double eps=1e-10;
 	const double PI=3.1415926535;
//priority_queue<int , vector<int >, greater<int >> q;
//priority_queue<int > q;
//map<string ,int>mp,mmp;
 //typedef pair<int ,int > PII;
//stack < PII > p;
 
//queue<int > q;
//char s1[2020],s2[2020];
//vector<vector<int>> c(n+13,vector<int>(m+3));
//map<int,int>mp;
 
//priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q[1001][1001],p;
 //a.erase(unique(a.begin(), a.end()), a.end());
//char p,q;
//char s[N];
//deque<int > q;
//queue<int> q;
//using ull = unsigned long long;
//ull mod=212370440130137957ll;

int ma,mi;
int  n,m;

//int f[N][N],a[N][N],b[N][N],c[N][N],dp[N][N],q[N],v[N][N];

//
//struct node
//{
//	
//	double x,y,z;
//	
//}p[N];
//
//inline bool cmp(node w,node v)
//{
//	if(w.x==v.x)
//		return w.y<v.y;
//		
//	return w.x<v.x;	
//}

//
//int fx[5]={-1,0,0,1};
//int fy[5]={0,-1,1,0};


//int q[N],q2[N];


//知道3边,判断是否可以组成三角形 
bool check(int x,int y,int z) 
{
	if(x+y>z&&x+z>y&&y+z>x) return 1;
	return 0;
}
//知道3边,求三角形面积 
double df(double x,double y,double z)
{
	double p=(x+y+z)/2;
	return sqrt(p*(p-x)*(p-y)*(p-z));
}

char ss[N];

signed main()
{
	std::ios::sync_with_stdio(false);//取消cin与stdin同步,加速读入 
	cin.tie(0);cout.tie(0);
 	int t;
 	t=1;
 	//string s;
	cin>>t;

	while(t--)
	{
		int tt=0,fa=0,ans=0;
		//int   res=0,ans=0.0;
		//ma=0,mi=2e17;
		//map<int,int> mp,mp2;
		cin>>n>>m;
		vector<int> a(n+3),la(m+2),fi(m+2),ne(m+2),x(m+3),y(m+3),now(n+3);
		set<pair<int,int > > se;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			now[i]=a[i];
		}
		
		for(int i=1;i<=m;i++)
		{
			cin>>x[i]>>y[i];
			if(!fi[y[i]])
			{
				fi[y[i]]=i;
			}	
			if(la[y[i]])
			{
				ne[la[y[i]]]=i;
			}			
			la[y[i]]=i;
		}	
		
		for(int i=1;i<=m;i++)
		{
			if(!ne[i])
			{
				ne[i]=m+1;
			}
		}
		
		for(int i=1;i<=n;i++)
		{
			if(fi[i])
			{
				se.insert({fi[i],i});
			}
			else
			{
				se.insert({m+1,i});
			}
		}
		int dis=0,res=0;
		for(int i=1;i<=m;i++)
		{
			res=x[i]-x[i-1];
			while(se.size()&&res>=now[se.begin()->second])
			{
				res-=now[se.begin()->second];
				
				ans+=now[se.begin()->second];
				now[se.begin()->second]=0;
				se.erase(se.begin());
			}
			if(res&&se.empty())
			{
				
				break;
			}
			
			now[se.begin()->second]-=res;
			
			if(se.find({i,y[i]})!=se.end())
				se.erase({i,y[i]});
			se.insert({ne[i],y[i]});
			
			now[y[i]]=a[y[i]];
	
			ans+=res;
			
		//	cout<<ans<<"\n";
		}
		while(se.size())
		{
			ans+=now[se.begin()->second];
			se.erase(se.begin());
		}
		cout<<ans;
		cout<<"\n";
	}
	
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1

output:

12
9

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

6
3 2
2 2 2
6 1
7 1
2 2
3 3
2 1
6 2
2 3
2 2
5 1
7 2
9 1
2 2
3 3
2 1
6 2
1 1
999999999
1000000000 1
1 1
1000000000
1000000000 1

output:

9
11
4
11
999999999
2000000000

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 87ms
memory: 13912kb

input:

10
230 8042
599 1039 69 1011 1366 824 14117 1523 806 5002 332 55 3769 996 359 1040 255 1135 3454 3609 6358 2509 3695 8785 3890 1304 3394 14611 33 89 2245 508 22 1043 10411 628 1279 714 903 585 7413 5099 845 148 4689 2110 8683 1613 143 3263 2599 110 244 3297 4742 1571 425 1822 15692 572 9397 328 1691...

output:

1543020
1578939
1526016
1527381
1547404
1564631
1051729
1548178
1114634
1072253

result:

ok 10 lines

Test #4:

score: 0
Accepted
time: 129ms
memory: 14908kb

input:

3
100000 100000
1 2 1 1 10 1 17 34 1 1 20 14 4 24 3 1 3 2 7 4 6 3 1 18 1 4 2 1 3 8 3 2 4 1 10 4 23 14 4 16 4 9 8 3 5 2 6 2 2 3 1 7 3 25 10 3 5 3 1 2 14 3 1 3 8 19 3 4 5 7 4 22 2 2 3 3 8 11 8 8 1 9 1 4 2 10 9 8 13 7 21 14 1 27 4 3 2 13 8 1 3 1 5 1 1 1 12 3 4 2 4 10 2 2 10 2 2 14 1 11 1 1 6 1 1 1 2 4 ...

output:

1117713
1116035
1092827

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 135ms
memory: 15048kb

input:

3
100000 100000
2086 178 3183 10562 8083 1408 4312 2370 4331 1721 2154 6155 7176 1991 30048 7425 9493 1709 7640 3726 182 2462 1597 2865 649 8069 3419 6510 8556 680 49 68 9820 13378 799 2489 1466 8877 8695 2235 915 2579 524 6615 20680 7704 4325 4696 8853 5492 1417 4342 1740 2355 2255 5297 15035 5003 ...

output:

1099515229
1100014648
1105660500

result:

ok 3 lines

Test #6:

score: -100
Runtime Error

input:

100
13 889
5025 26312 1491 20523 204842 40921 5217 25853 24382 141405 54635 22605 118412
322 6
947 11
1292 7
1623 12
2338 11
5106 10
6276 5
6431 13
7597 2
8146 7
8453 7
8584 4
8707 6
9101 9
9893 2
11005 4
11485 8
13038 13
14944 3
15446 10
15628 8
19159 11
22478 8
22578 4
22766 6
23126 9
23751 4
2428...

output:


result: