QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879079#8035. Call Me Call Mesz051ML 7639ms1013780kbC++202.8kb2025-02-01 20:53:562025-02-01 20:53:57

Judging History

This is the latest submission verdict.

  • [2025-02-06 18:39:16]
  • hack成功,自动添加数据
  • (/hack/1529)
  • [2025-02-01 20:53:57]
  • Judged
  • Verdict: ML
  • Time: 7639ms
  • Memory: 1013780kb
  • [2025-02-01 20:53:56]
  • Submitted

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <stack>
#include <random>
#include <map>
#define int long long
using namespace std; 

void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
int lg(int k){
	return k==0?-1:__lg(k);
}
struct Alarm{
	int qlim[1100010],qh[1100010],delt[1100010],qcnt=0;
	vector<int> qp[1100010];
	vector<int> seps[1100010][20];
	int sum[1100010];
	Alarm(){}
	int insert(vector<int> pos,int lim){
		qlim[++qcnt]=lim;
//		printf("[+%lld]:",qcnt);
//		for(int i:pos){
//			printf("%lld ",i);
//		}
//		putchar('\n');
		qp[qcnt]=pos;
		qh[qcnt]=20;
		while(qh[qcnt]>=0){
			int cur=0;
			for(int i:pos){
				cur+=sum[i]|((1ll<<qh[qcnt])-1);
			}
			if(cur>=lim){
				qh[qcnt]--;
			}else{
				break;
			}
		}
		for(int i:pos){
			seps[i][qh[qcnt]+1].push_back(qcnt);
		}
		return qcnt;
	}
	vector<int> update(int k,int v){
		vector<int> res;
		int tp=lg(sum[k]^(sum[k]+v));
		sum[k]+=v;
		for(int p=-1;p<=tp;p++){
			vector<int> tmp=seps[k][p+1];
			seps[k][p+1].clear();
			for(int i:tmp){
				//printf("[%lld %lld %lld]",k,p,i);
				if(qh[i]!=p){
					continue;
				}
				while(qh[i]>=0){
					int cur=0;
					for(int j:qp[i]){
						cur+=sum[j]|((1ll<<qh[i])-1);
					}
					if(cur>=qlim[i]){
						qh[i]--;
					}else{
						break;
					}
				}
				if(qh[i]==-1){
					res.push_back(i);	
				}else{
					if(qh[i]==p){
						seps[k][p+1].push_back(i);
					}else{
						for(int j:qp[i]){
							seps[j][qh[i]+1].push_back(i);
						}
					}
				}
			}
		}
		return res;
	}
} alarm;
int n;
vector<int> cur;
void update(int k,int curl,int curr,int ql,int qr){
	if(ql<=curl && curr<=qr){
		cur.push_back(k);
	}else{
		int mid=(curl+curr)>>1;
		if(ql<=mid){
			update(k*2,curl,mid,ql,qr);
		}
		if(mid<qr){
			update(k*2+1,mid+1,curr,ql,qr);
		}
	}
}
void query(int k,int curl,int curr,int pos){
	cur.push_back(k);
	if(curl!=curr){
		int mid=(curl+curr)>>1;
		if(pos<=mid){
			query(k*2,curl,mid,pos);
		}else{
			query(k*2+1,mid+1,curr,pos); 
		}
	}
}
signed main(){
	read(n);
	int l,r,v;
	vector<int> tmp;
	int res=0;
	for(int i=1;i<=n;i++){
		read(l);
		read(r);
		read(v);
		if(!v){
			tmp.push_back(i);
			alarm.qcnt++;
			continue;
		}
		update(1,1,n,l,r);
		alarm.insert(cur,v);
		cur.clear();
	}
	while(tmp.size()){
		res+=tmp.size();
		vector<int> nw;
		for(int i:tmp){
			cur.clear();
			query(1,1,n,i);
			for(int j:cur){
				vector<int> vt=alarm.update(j,1);
				for(int p:vt){
					nw.push_back(p);
				}
			}
		}
		tmp=nw;
	}
	printf("%lld",res);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 56ms
memory: 548556kb

input:

3
2 3 2
2 3 1
2 2 0

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 54ms
memory: 550660kb

input:

3
2 3 1
2 3 2
2 2 0

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 62ms
memory: 546252kb

input:

50
32 49 11
7 9 3
29 46 2
28 43 14
14 24 12
9 35 26
5 23 5
34 49 7
8 40 28
21 45 19
14 20 8
23 24 0
14 50 9
3 36 12
44 45 2
9 50 2
11 20 8
9 28 17
15 33 0
11 50 21
2 5 2
13 41 27
5 41 18
5 18 2
2 11 1
3 19 9
24 46 9
3 14 13
37 44 5
4 40 23
3 32 6
24 38 13
45 45 1
44 50 0
37 49 0
3 15 12
21 23 3
31 3...

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 57ms
memory: 550568kb

input:

200
11 196 37
68 186 104
36 55 17
37 180 60
106 149 43
26 67 3
81 140 25
130 136 8
38 118 59
140 187 11
44 66 24
117 145 15
140 147 9
26 105 1
82 107 7
51 66 15
38 113 9
71 89 7
2 87 51
123 127 1
19 24 1
60 177 90
134 153 5
10 125 75
49 60 0
158 185 21
91 165 27
80 199 44
137 173 30
52 127 71
13 40 ...

output:

80

result:

ok 1 number(s): "80"

Test #5:

score: 0
Accepted
time: 60ms
memory: 545604kb

input:

500
62 73 6
80 197 86
424 463 40
34 402 9
288 482 56
358 479 130
120 463 375
156 381 149
237 442 31
136 334 132
23 328 229
243 331 34
241 376 17
29 31 3
130 241 40
70 119 25
179 469 64
400 438 26
137 495 125
247 462 137
76 422 169
49 220 177
177 184 6
95 306 116
62 292 7
120 163 4
311 413 95
263 486...

output:

400

result:

ok 1 number(s): "400"

Test #6:

score: 0
Accepted
time: 53ms
memory: 550856kb

input:

500
374 422 22
220 426 21
389 432 36
289 375 44
220 408 175
181 326 107
41 202 79
57 81 22
249 467 119
465 486 13
169 305 53
56 82 5
78 123 41
146 200 4
168 216 43
198 360 67
52 216 147
188 489 15
172 204 6
32 165 131
259 496 98
94 362 199
12 357 156
382 427 7
341 486 14
99 333 19
104 288 46
11 383 ...

output:

350

result:

ok 1 number(s): "350"

Test #7:

score: 0
Accepted
time: 54ms
memory: 548684kb

input:

1000
302 839 526
517 777 307
375 822 654
253 777 577
105 815 775
297 975 460
115 375 325
104 494 214
196 842 646
297 745 7
156 483 385
379 670 105
536 880 402
159 831 522
18 649 544
85 590 2
239 948 788
112 570 550
311 413 88
744 788 33
130 241 10
28 354 74
21 869 172
294 306 11
58 623 768
39 685 73...

output:

100

result:

ok 1 number(s): "100"

Test #8:

score: 0
Accepted
time: 2056ms
memory: 782036kb

input:

400000
131626 262151 44708
33479 241968 596
156448 380747 73026
306027 333202 25023
223679 234561 9636
41148 315180 174749
110638 143248 27373
108072 316650 32460
101258 286892 49767
60238 200451 106857
144354 230616 41442
8975 116525 68828
58197 247012 6720
5643 8825 2602
131228 351692 161752
13415...

output:

40000

result:

ok 1 number(s): "40000"

Test #9:

score: 0
Accepted
time: 4138ms
memory: 877068kb

input:

400000
181217 382285 205356
5705 73736 23752
48595 113165 64097
68312 114513 44447
93853 288834 132497
134992 195534 31661
83479 112995 3546
30704 246119 40652
281857 290766 5499
28559 360030 299701
180493 384483 10220
43438 256886 29238
229757 243344 11621
36919 208568 146843
155448 302838 4387
844...

output:

120000

result:

ok 1 number(s): "120000"

Test #10:

score: 0
Accepted
time: 6354ms
memory: 965824kb

input:

400000
117191 164491 15948
484 137917 157790
265247 389104 36514
128495 347689 52466
148140 287177 39902
16682 158712 27455
74903 196155 109486
70192 89056 378
102731 389519 305820
34940 104964 49231
108688 141832 8839
12469 266732 202406
317225 358728 42272
114380 199477 1780
331462 348078 2571
426...

output:

200000

result:

ok 1 number(s): "200000"

Test #11:

score: 0
Accepted
time: 7639ms
memory: 1013780kb

input:

400000
56701 153019 5331
126457 159230 1335
176892 192753 1185
68188 209115 16352
136777 190708 8678
13333 181758 332282
356419 368268 1043
328377 396298 29741
49133 327611 7165
9582 297993 2409
5645 121562 12942
152850 321505 759
314206 361734 91071
180080 322089 3295
53071 313313 55349
237779 2819...

output:

280000

result:

ok 1 number(s): "280000"

Test #12:

score: -100
Memory Limit Exceeded

input:

400000
79659 124493 44197
67032 92654 392
194215 254446 19355
167525 367972 66222
182433 263989 412
173681 327730 60345
177776 286446 45010
22536 359993 307582
361335 362147 301
77438 315590 26255
664 6695 41
112967 215181 98671
37395 68991 29048
137625 245562 84575
27135 261661 166078
83555 208275 ...

output:

360000

result: