QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311751#8014. 新本格魔法少女Clonoth0 0ms0kbC++205.0kb2024-01-22 18:48:322024-01-22 18:48:32

Judging History

This is the latest submission verdict.

  • [2024-01-22 18:48:32]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2024-01-22 18:48:32]
  • Submitted

answer

#include<stdio.h>
#include<bits/stdc++.h>
#define fir first
#define sec second
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef __int128 int128;
typedef __uint128_t uint128;
typedef pair<int,int> pii;
template<typename type>
inline void chmin(type &x,const type &y)
{
	if(y<x)
		x=y;
}
template<typename type>
inline void chmax(type &x,const type &y)
{
	if(x<y)
		x=y;
}
constexpr int Max=5e5+10;
struct block_array1//O(1) modify
{
	static constexpr int block=707,Size=Max/block+2;
	ll s1[Max],s2[Size];
	inline void add(const uint &x,const ll &k)
	{
//		cerr<<"add "<<x<<" : "<<k<<"\n";
		s1[x]+=k,s2[x/block]+=k;
	}
	inline ll ask(const int &x)const
	{
		const int p=x/block,rb=min((p+1)*block,Max);
		ll ans=0;
		for(int i=x;i<rb;++i)
			ans+=s1[i];
		for(int i=p+1;i<Size;++i)
			ans+=s2[i];
//		cerr<<"ask "<<x<<" : "<<ans<<"\n";
		return ans;
	}
	inline void clear()
	{
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
	}
}t;
struct block_array2//O(1) query
{
	static constexpr int block=707,Size=Max/block+2;
	ll s1[Max+block+1],s2[Size];
	inline void add(const int &x,const ll &k)
	{
		const int p=x/block;
		for(int i=p*block;i<=x;++i)
			s1[i]+=k;
		for(int i=0;i<=p;++i)
			s2[i]+=k;
	}
	inline ll ask(const int &x)const
	{
		const int p=x/block;
		return s1[x]+(p+1<Size?s2[p+1]:0);
	}
	inline void clear()
	{
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
	}
}t0,t1;
constexpr int block_cnt=Max;
int n,m,q_cnt;
vector<pii>Q[Max];
int block,tot;
int lpos[block_cnt],rpos[block_cnt],bel[Max];
void init_block()
{
	block=min(n,4000);
	tot=(n+block-1)/block;
	for(int i=1;i<=tot;++i)
		lpos[i]=rpos[i-1]+1,rpos[i]=rpos[i-1]+block;
	rpos[tot]=n;
	for(int i=1;i<=tot;++i)
		for(int j=lpos[i];j<=rpos[i];++j)
			bel[j]=i;
//	cerr<<"block : ";
//	for(int i=1;i<=tot;++i)
//		cerr<<"["<<lpos[i]<<","<<rpos[i]<<"] ";
//	cerr<<"\n";
}
int opt[Max],a[Max],b[Max],c[Max];
int pos[Max],num[Max];
int id[block_cnt],tag[block_cnt];
ll ans[Max];
signed main()
{
	freopen("mfsn.in","r",stdin);
	freopen("mfsn.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>q_cnt;
	init_block();
	for(int i=1;i<=m;++i)
	{
		cin>>opt[i]>>a[i]>>b[i];
		if(opt[i]==1)
			cin>>c[i];
	}
	for(int i=1,l,r;i<=q_cnt;++i)
		cin>>l>>r,Q[r].emplace_back(l,i);
	for(int o=1;o<=m;++o)
	{
		const int l=a[o],r=b[o];
		const int p=bel[l],q=bel[r];
		auto push_down=[&](const int &u)->void
		{
			if(tag[u])
			{
				const int x=tag[u],y=id[u];
				const int lb=lpos[u],rb=rpos[u];
				for(int i=lb;i<=rb;++i)
					num[i]=x,pos[i]=y;
				tag[u]=0;
			}
		};
		auto update_block=[&](const int &u,int l,int r,const int &k)->void
		{
			const int lb=lpos[u],rb=rpos[u];
			if(l<=lb&&r>=rb)
				tag[u]=k,id[u]=o;
			else
			{
				chmax(l,lb),chmin(r,rb);
				if(l>r)
					return;
				push_down(u);
				for(int i=l;i<=r;++i)
					num[i]=k,pos[i]=o;
			}
		};
		auto query_block=[&](const int &u,int l,int r)->void
		{
			const int lb=lpos[u],rb=rpos[u];
			if(l<=lb&&r>=rb)
			{
				if(tag[u])
					t.add(id[u],(ll)(rb-lb+1)*tag[u]);
			}
			else
			{
				chmax(l,lb),chmin(r,rb);
				if(l>r)
					return;
				if(tag[u])
					t.add(id[u],(ll)(r-l+1)*tag[u]);
				else
					for(int i=l;i<=r;++i)
						t.add(pos[i],num[i]);
			}
		};
		if(opt[o]==1)
			for(int i=p;i<=q;++i)
				update_block(i,l,r,c[o]);
		else
			for(int i=p;i<=q;++i)
				query_block(i,l,r);
		for(auto [x,id]:Q[o])
			ans[id]+=t.ask(x);
	}
	memset(pos,0,sizeof(pos));
	memset(num,0,sizeof(num));
	for(int z=1;z<=tot;++z)
	{
		const int lb=lpos[z],rb=rpos[z];
		int cnt=0,tag=0,id=0;
		for(int o=1;o<=m;++o)
		{
			if(opt[o]==2)
			{
				if(a[o]<=lb&&b[o]>=rb)
					++cnt;
			}
			else
			{
				int l=max(a[o],lb),r=min(b[o],rb);
				const int w=c[o];
				if(l<=r)
				{
					auto clear=[&](int l,int r)->void
					{
						for(int i=l,j;i<=r;i=j+1)
						{
							j=i;
							const int x=pos[i];
							while(j<r&&pos[j+1]==x)
								++j;
							if(x)
							{
								t1.add(x,-(ll)(j-i+1)*num[i]);
								t0.add(x,(ll)(j-i+1)*num[i]*cnt);
							}
							for(int k=i;k<=j;++k)
								pos[k]=0;
						}
					};
					if(tag&&(l>lb||r<rb))
					{
						clear(lb,rb);
						for(int i=lb;i<=rb;++i)
							num[i]=tag,pos[i]=id;
						t1.add(id,(ll)(rb-lb+1)*tag);
						t0.add(id,-(ll)(rb-lb+1)*tag*cnt);
						tag=0;
					}
					if(!tag)
						clear(l,r);
					if(l==lb&&r==rb)
						tag=w,id=o;
					else
					{
						tag=0;
						for(int i=l;i<=r;++i)
							num[i]=w,pos[i]=o;
						t1.add(o,(ll)(r-l+1)*w);
						t0.add(o,-(ll)(r-l+1)*w*cnt);
					}
				}
			}
			for(auto [x,id]:Q[o])
				ans[id]+=t0.ask(x)+cnt*t1.ask(x);
		}
		t0.clear(),t1.clear();
	}
	for(int i=1;i<=q_cnt;++i)
		cout<<ans[i]<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

100 100 100
2 80 86
2 15 49
1 11 100 25
2 22 36
2 37 100
1 14 16 49
2 74 90
2 28 76
1 43 45 78
1 54 56 27
1 73 75 29
2 34 81
2 51 90
1 13 14 52
1 72 73 2
2 18 58
2 44 58
1 83 85 30
1 86 88 69
1 29 31 25
1 92 94 19
1 48 49 16
1 55 57 91
1 98 100 42
2 13 96
2 50 83
1 23 25 39
1 84 85 55
1 43 45 5
1 90...

output:


result:


Test #2:

score: 0
Dangerous Syscalls

input:

100 100 100
1 56 92 5
1 5 9 91
1 70 92 77
1 45 52 90
1 37 38 36
1 9 10 1
2 1 72
1 79 80 86
2 40 98
1 96 97 89
2 46 78
2 41 58
1 57 58 65
1 73 74 44
1 20 21 54
1 95 96 61
1 23 24 40
1 60 61 48
1 17 18 65
1 43 44 68
1 44 45 7
1 28 29 4
1 10 11 37
1 14 15 44
1 69 70 18
1 33 34 52
1 15 16 67
1 62 63 64
...

output:


result:


Test #3:

score: 0
Dangerous Syscalls

input:

5000 5000 5000
1 4070 5000 3145
2 1139 3698
1 798 799 3999
1 2423 2424 2414
1 836 838 518
1 3605 3607 2831
1 525 526 2041
1 4734 4736 1862
2 2408 3821
1 1394 1395 1129
2 601 3026
2 728 4428
1 567 569 4843
2 4235 4835
1 3568 3569 1157
1 3043 3045 4342
1 1813 1815 1888
1 2992 2993 4810
1 1862 1864 112...

output:


result:


Test #4:

score: 0
Dangerous Syscalls

input:

5000 5000 5000
1 3198 5000 2085
1 2688 2781 3934
1 663 664 1655
1 472 473 4369
1 822 823 75
2 798 2403
1 518 519 4434
1 4022 4023 3962
1 121 122 1996
1 568 569 2710
1 2908 2909 418
1 429 430 4757
1 1361 1362 4590
1 4439 4440 4849
1 3104 3105 2808
1 78 79 1549
1 2111 2112 2281
1 3405 3406 4240
1 2739...

output:


result:


Test #5:

score: 0
Dangerous Syscalls

input:

4997 5000 4997
1 924 4997 4123
1 1508 1568 759
1 1148 1190 3389
1 908 952 122
1 4976 4997 4100
1 4578 4637 1736
1 2780 2821 3570
1 2830 2874 1796
1 351 391 1
1 762 801 3091
1 2060 2105 398
1 4572 4618 615
1 941 971 853
1 4395 4397 4934
1 4573 4574 4506
1 3697 3698 83
2 112 2024
1 310 311 1941
1 2116...

output:


result:


Test #6:

score: 0
Dangerous Syscalls

input:

4997 4999 4996
2 4368 4799
2 2119 4764
2 4434 4464
1 2035 4706 4296
1 519 522 2387
2 3 2084
1 4748 4755 461
2 2812 4626
1 4801 4805 2427
1 611 615 2155
2 772 2397
2 1443 2197
2 392 792
1 3032 3036 2776
2 3148 4757
1 3661 3678 3968
1 3901 3921 2378
1 143 164 531
1 3337 3360 3189
2 679 2911
1 1436 145...

output:


result:


Test #7:

score: 0
Dangerous Syscalls

input:

499998 499998 500000
2 45317 481911
2 205023 267850
2 229212 496395
2 311928 408362
2 60781 309919
2 5271 471569
2 428188 498422
2 92261 439291
2 169892 354633
2 154209 351949
2 39872 442239
2 17793 200874
2 111458 165313
2 35630 448969
2 144408 434923
2 150127 486605
2 87239 425125
2 221549 283735
...

output:


result:


Test #8:

score: 0
Dangerous Syscalls

input:

499996 500000 499996
2 416226 432058
2 352324 435508
2 284349 418508
2 331919 481387
2 123642 260653
2 443789 449866
2 304455 480845
2 25402 269023
2 88509 334117
2 91159 399658
2 354630 412055
2 27378 126849
2 43994 304769
2 352338 413477
2 441505 499446
2 230203 287653
2 386 34219
2 77130 483544
2...

output:


result:


Test #9:

score: 0
Dangerous Syscalls

input:

499999 499997 499996
1 242721 499999 95404
2 46103 133768
2 374074 441419
1 24121 24525 460791
1 296358 334367 213389
1 333891 339996 192126
2 271641 289312
1 159292 235107 359363
2 281766 283959
2 68186 255669
2 112532 201134
2 281439 287449
2 265345 398433
1 495720 499897 85179
2 336233 383598
1 3...

output:


result:


Test #10:

score: 0
Dangerous Syscalls

input:

499996 499998 499996
2 127334 135648
2 250092 494065
2 202618 237080
1 365995 485247 159366
1 461761 461763 167619
1 161295 165395 156081
2 118953 278863
1 31995 32188 13920
2 211226 376698
2 125014 312511
1 248692 248694 369316
2 23909 438451
1 90793 222688 109394
1 405548 405549 283104
2 54420 263...

output:


result:


Test #11:

score: 0
Dangerous Syscalls

input:

499999 499996 500000
1 263967 499999 193060
1 473673 473677 256364
1 112817 112820 147747
2 47560 75007
1 19751 19754 272463
1 147343 147345 432368
1 385248 385251 111981
1 98114 98117 384182
1 186894 186898 304739
1 13283 13285 1641
1 127923 127925 168790
2 59949 123247
2 76677 91972
1 138037 13803...

output:


result:


Test #12:

score: 0
Dangerous Syscalls

input:

499999 499995 499997
1 163879 499999 440480
2 420164 470414
1 443882 499999 62525
1 313171 499999 294789
1 469407 469540 44668
2 25119 191405
2 172689 455667
2 110136 338451
2 218391 398188
1 486533 486654 93435
2 95706 256203
2 196989 304612
2 326480 401308
2 54460 198784
1 271793 271898 320340
2 9...

output:


result:


Test #13:

score: 0
Dangerous Syscalls

input:

200000 200000 200000
2 31803 80740
2 112818 127167
1 131322 154428 90611
2 11014 192282
2 41925 115417
2 5816 159028
2 111819 126655
2 37293 172866
2 27835 145099
2 124446 162824
2 104521 118016
2 40376 127391
1 195318 195319 149596
2 41040 179839
2 61847 94626
2 69878 181705
2 28968 179132
2 132543...

output:


result:


Test #14:

score: 0
Dangerous Syscalls

input:

199995 199998 199998
1 159195 199995 13044
2 86976 157151
1 64762 102114 152625
1 61813 63647 178420
1 82889 85481 125381
1 51586 54321 77506
2 45182 109756
1 181575 184132 133556
2 28331 132281
2 17325 40861
2 42257 191103
2 147228 198059
2 75171 155696
1 139100 140799 154126
1 188327 190311 76827
...

output:


result:


Test #15:

score: 0
Dangerous Syscalls

input:

199999 199996 200000
1 179926 199999 32711
1 1042 1044 112146
2 26640 43359
1 178347 178351 169789
2 32064 164957
2 81951 117742
1 179853 179856 73377
2 66862 193241
2 10596 28181
2 49117 162750
1 13331 13333 43998
2 26996 197910
1 161366 161369 84391
2 127515 184183
1 66412 66416 97202
2 49708 5634...

output:


result:


Test #16:

score: 0
Dangerous Syscalls

input:

200000 200000 200000
1 59821 200000 173244
1 190307 190309 110936
1 112341 112342 4761
1 124738 124740 84834
1 3047 3049 102534
2 114052 180833
2 72832 109679
2 84797 91295
1 191583 191584 141834
1 185318 185320 87703
1 117000 117002 109533
1 80539 80540 105603
1 24207 24209 111543
1 83298 83299 140...

output:


result:


Test #17:

score: 0
Dangerous Syscalls

input:

500000 500000 500000
2 430331 460074
1 364723 500000 100669
1 250319 250342 82754
1 438542 441692 403146
1 463281 463283 433598
2 257762 468063
2 48944 155558
2 353640 481169
1 84674 84675 290827
2 146697 229831
2 468564 488452
2 5108 66751
1 23182 45112 201883
2 282890 447793
1 32871 33375 376198
1...

output:


result:


Test #18:

score: 0
Dangerous Syscalls

input:

500000 499995 499999
2 227886 411572
2 211683 333769
1 250096 500000 235662
1 426728 426927 304290
2 57626 245045
2 274989 390864
2 128937 178776
1 131741 131862 102941
1 98436 98438 22052
1 166478 166479 223278
1 450334 450336 468682
1 235946 235947 469845
1 472838 472839 386149
1 94197 94199 37254...

output:


result:


Test #19:

score: 0
Dangerous Syscalls

input:

500000 500000 500000
1 483553 500000 33628
1 469113 469115 99122
2 331771 461807
2 132277 227909
1 409018 409020 67790
2 239961 327023
2 71363 250145
2 194504 394975
2 112739 357223
2 29586 226312
1 365927 365929 56596
2 37108 464107
2 260079 467849
1 132248 132250 77986
2 192853 237448
2 361959 386...

output:


result:


Test #20:

score: 0
Dangerous Syscalls

input:

499999 499999 499996
2 212908 238055
1 460268 499999 317714
2 420753 465452
1 184130 194219 347230
1 24358 31202 484414
2 261874 280744
1 382916 389593 121902
2 998 230297
1 83691 94553 138191
2 357537 469176
1 478043 489289 9664
2 49390 163924
1 496313 499999 485644
2 307553 482205
1 148359 158827 ...

output:


result: