QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#656277#7744. ElevatorDixiky_215AC ✓42ms8104kbC++203.0kb2024-10-19 12:09:372024-10-19 12:09:41

Judging History

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

  • [2024-10-19 12:09:41]
  • 评测
  • 测评结果：AC
  • 用时：42ms
  • 内存：8104kb
查看
  • [2024-10-19 12:09:37]
  • 提交

answer

#include <bits/stdc++.h>		
using namespace std;
using ll = long long;
const int MAXN=1e6+7;
const ll mod=998244353LL;
int n,t;
ll m;
bool vis[MAXN];
ll ton[MAXN/3][3];
int tot=0,s[MAXN];
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		tot=0;
		for(int i=1;i<=n;i++)
		{
			ll v;
			int idk,sss;
			cin>>v>>idk>>sss;
			ton[sss][idk]+=v;
			if(!vis[sss]) vis[sss]=1,s[++tot]=sss;
		}
		sort(s+1,s+1+tot);
		ll ans=0LL;
		int now_id=tot;
        ll sumk=m,maxl=0;
		for(int i=tot;i>=1;i--)
		{
			ll sk=s[i];
            if(sumk==1)
            {
                bool kkk=0;
                for(int j=now_id;j>=1;j--)
                {
                    if(ton[s[j]][1]>0)
                    {
                        kkk=1;
                        now_id=j;
                        ton[s[j]][1]--;
                        maxl=max(maxl,(ll) s[j]);
                        break;
                    }
                }
                if(!kkk) now_id=0;
                ans+=maxl;
                sumk=m;maxl=0LL;
            }
			if(sumk>=ton[sk][2]*2LL)
            {
                sumk-=ton[sk][2]*2LL;
                if(ton[sk][2]>0) maxl=max(maxl,sk);
                ton[sk][2]=0LL;
            }
            else
            {
                if(sumk>0) maxl=max(maxl,sk);
                ton[sk][2]-=sumk/2;
                sumk=sumk%2LL;
                if(sumk%2)
                {
                    bool kkk=0;
                    for(int j=now_id;j>=1;j--)
                    {
                        if(ton[s[j]][1]>0)
                        {
                            kkk=1;
                            now_id=j;
                            ton[s[j]][1]--;
                            maxl=max(maxl,(ll) s[j]);
                            break;
                        }
                    }
                    if(!kkk) now_id=0;
                }
                ans+=maxl;

                ll numk=ton[sk][2]/(m/2LL);
                ans+=numk*sk;
                ton[sk][2]%=(m/2);
                
                sumk=m-ton[sk][2]*2;maxl=0LL;
                if(ton[sk][2]>0) maxl=max(maxl,sk);
                ton[sk][2]=0;
            }
            
            if(sumk>=ton[sk][1])
            {
                sumk-=ton[sk][1];
                if(ton[sk][1]>0) maxl=max(maxl,sk);
                ton[sk][1]=0LL;
            }
            else
            {
                if(sumk>0) maxl=max(maxl,sk);
                ton[sk][1]-=sumk;

                ans+=maxl;

                ll numk=ton[sk][1]/m;
                ans+=sk*numk;
                ton[sk][1]%=m;

                sumk=m-ton[sk][1];maxl=0;
                if(ton[sk][1]>0) maxl=max(maxl,sk);
                ton[sk][1]=0;
            }
			
		}
        if(sumk!=m) ans+=maxl;
		cout<<ans<<'\n';
		for(int i=1;i<=tot;i++)
		{
			ton[s[i]][1]=ton[s[i]][2]=0LL;
			vis[s[i]]=0;
		}
	}
	return 0;
}
/*
aabbaA
		
*/
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7672kb

input:

2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345

output:

24
100000

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 29ms
memory: 7836kb

input:

5501
8 104
5 2 3
6 2 4
5 2 3
6 2 9
8 2 4
2 1 3
7 2 4
8 2 8
1 290
3 1 1
12 12
6 1 2
1 2 2
1 1 2
1 2 4
6 1 1
1 2 5
6 1 4
4 1 4
6 2 4
6 2 5
4 2 5
4 1 4
5 334
1 1 4
1 2 3
4 2 1
5 1 1
2 1 2
13 218
5 2 3
5 1 4
1 2 1
1 2 5
3 2 2
1 1 3
4 2 2
1 2 5
2 2 1
2 1 5
3 2 1
5 2 1
1 1 4
10 260
7 2 1
5 1 1
5 2 4
6 1 6...

output:

9
1
23
4
5
7
1
3
9
6
1
10
4
9
17
6
4
1
8
5
5
7
1
3
23
6
3
3
2
2
2
3
8
1
5
6
9
11
147
7
10
2
7
7
8
6
5
5
1
7
3
5
10
7
7
10
8
1
4
2
3
9
1
5
2
9
1
6
7
7
6
10
18
8
10
4
10
9
2
8
3
5
9
3
6
5
3
2
6
1
3
2
2
1
6
9
6
3
4
8
9
9
2
6
1
2
6
7
5
2
5
21
8
1
2
3
4
9
3
4
6
5
9
6
1
7
3
7
3
2
2
8
7
3
5
9
7
10
7
3
2
4
...

result:

ok 5501 lines

Test #3:

score: 0
Accepted
time: 37ms
memory: 8104kb

input:

3
100000 8
8 2 6
7 2 8
5 1 10
7 2 7
4 1 7
6 2 9
7 1 2
3 1 1
5 1 10
5 1 1
3 2 10
5 2 5
7 1 6
5 2 7
7 2 1
5 1 6
2 2 10
8 1 7
7 1 1
10 2 6
9 1 1
8 1 4
10 1 4
6 1 1
4 1 4
1 2 9
3 2 6
6 1 3
4 1 7
9 2 5
8 2 4
7 2 1
2 2 10
6 2 9
3 1 3
2 2 3
2 2 4
7 2 4
8 1 1
5 2 3
5 2 7
7 2 9
1 1 4
5 1 2
2 1 9
3 2 1
9 2 2
...

output:

568601
4708350936
93900404329230

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 42ms
memory: 8008kb

input:

3
100000 174
90429 1 64237
30851 1 44358
63571 2 89174
20391 2 28747
13561 2 88689
81508 2 28383
85733 1 5777
37524 2 34730
10588 2 88519
61493 2 83682
55885 1 65270
17669 2 63015
85387 1 64757
91420 2 74020
9067 2 91750
20809 1 52771
36478 2 17941
62064 1 36433
72912 2 6100
53923 2 73971
65825 2 39...

output:

2156004461915
884586357480
59034901233

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 42ms
memory: 8012kb

input:

3
100000 4418822
19907 1 13081
59730 2 93611
35050 1 5867
87777 1 21890
18374 1 82418
79526 2 76106
33510 2 45826
75573 1 42240
35449 1 98727
80720 2 65290
32021 2 51348
52399 2 97828
75498 2 51728
89905 1 22825
2855 1 26204
11427 1 99583
55530 2 37895
22256 2 92230
19533 1 9142
16138 1 54018
53102 ...

output:

84699074
270668
100000

result:

ok 3 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-30 18:48:08 | OpenSource Project