QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713987#1286. Ternary String CountingAzusaML 303ms235032kbC++145.2kb2024-11-05 21:10:082024-11-05 21:10:09

Judging History

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

  • [2024-11-05 21:10:09]
  • 评测
  • 测评结果:ML
  • 用时:303ms
  • 内存:235032kb
  • [2024-11-05 21:10:08]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=(a);i<=(n);++i)
#define per(i,a,n) for(int i=(n);i>=(a);--i)
#define SZ(x) ((int)(x).size())

using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=5e3+10,mod=1e9+7;

inline void rd(){};
template<typename T1,typename ...T2>
inline void rd(T1 &x,T2 &...rest){
    bool w=1; x=0; char ch=getchar();
    while(!isdigit(ch)){w^=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    w?0:x=-x;
    rd(rest...);
}

template<int MOD> struct mint {
    static const int mod = MOD;
    int v; 
    explicit operator int() const { return v; }
    mint():v(0) {}
    mint(ll _v) { 
        v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0) v += MOD; 
    }
    bool operator==(const mint& o) const {return v==o.v;}
    friend bool operator!=(const mint& a, const mint& b) {return !(a==b);}
    friend bool operator<(const mint& a, const mint& b) {return a.v<b.v;}
    mint& operator+=(const mint& o){ 
        if ((v += o.v) >= MOD) v -= MOD; 
        return *this; 
    }
    mint& operator-=(const mint& o){ 
        if ((v -= o.v) < 0) v += MOD; 
        return *this; 
    }
    mint& operator*=(const mint& o){ v=int((ll)v*o.v%MOD); return *this;}
    mint& operator/=(const mint& o) { return (*this) *= _inv(o); }
    friend mint pow(mint a, ll p) {
        mint ans = 1; 
        assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; 
    }
    friend mint _inv(const mint& a) { 
        assert(a.v != 0); 
        return pow(a,MOD-2);
    }
    mint operator-() const { return mint(-v); }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
};
using mi = mint<mod>;

int n,m;
vector<pii> event[maxn],h[maxn],w[maxn];
vector<int> val;
mi s[maxn],t[maxn];

inline void add(int x,int y,mi v){
	if(v==0) return;
	int nw=SZ(val);
	val.push_back((int)v);
	h[x].push_back({y,nw});
	w[y].push_back({x,nw});
	s[x]+=v; s[y]+=v;
}

inline void init(){
	rep(i,0,n){
		event[i].clear();
		h[i].clear();
		w[i].clear();
		s[i]=0;
	}
	val.clear();
}

inline void solve(){
	rd(n,m); 
	init();	
	rep(i,1,m){
		int l,r,x;
		rd(l,r,x);
		event[r].push_back({l,x});
	}
	add(0,0,1);
	rep(i,0,n){
		int jl=0,jr=n+1,kl=0,kr=n+1;
		for(auto [j,x]:event[i]){
			if(x==1) jr=min(jr,j-1);
			if(x==2) jl=max(jl,j),kr=min(kr,j-1);
			if(x==3) kl=max(kl,j);
		}
		rep(j,0,i){
			if(jl<=j && j<=jr) continue;
			for(auto [y,id]:h[j]){
				s[j]-=val[id]; s[y]-=val[id];
				val[id]=0;
			}
			h[j].clear();
		}
		rep(j,0,i){
			if(kl<=j && j<=kr) continue;
			for(auto [y,id]:w[j]){
				s[j]-=val[id]; s[y]-=val[id];
				val[id]=0;
			}
			w[j].clear();
		}
		if(i!=n){
			rep(j,0,i) t[j]=s[j];
			rep(j,0,i) add(i,j,t[j]);
		}
	}
	mi res=0;
	rep(i,0,n) res+=s[i];
	printf("%d\n",res/2);
}

signed main(){
    int _=1;
    scanf("%d",&_); 
    while(_--) solve();
}

詳細信息

Test #1:

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

input:

4
1 0
2 0
3 0
5 2
1 3 3
4 5 1

output:

3
9
27
18

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 4268kb

input:

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

output:

90
0
0
0
24300
0
0
0
768
0
0
972
2916
0
6480
864
0
0
0
0
0
0
0
0
6
0
0
0
0
0
96
0
6
0
0
0
0
0
0
0
108
0
0
0
2916
0
0
0
0
0
0
0
0
0
0
324
8748
0
0
0
0
0
0
4320
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
1992
0
0
450
0
162
1656
0
0
0
0
0
54
0
18
0
0
0
0
744
0
1620
324
0
0
36
36
0
0
60
6
54
0
0
0
0
0
0
0
0
243
810...

result:

ok 741 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 4348kb

input:

332
17 5
4 9 1
4 6 1
7 17 1
5 5 1
5 6 3
13 5
10 12 3
8 13 2
1 10 3
2 9 1
9 10 1
19 5
11 13 1
9 17 2
1 7 1
4 4 2
3 9 1
15 4
8 11 2
9 14 3
10 12 2
4 5 2
12 4
3 9 2
7 8 1
1 7 3
6 7 3
16 5
4 14 3
1 5 1
2 10 1
2 12 3
6 9 3
20 4
10 17 3
4 20 3
17 19 3
8 17 1
20 5
11 11 1
9 13 1
1 5 3
17 17 3
3 18 3
17 5
1...

output:

0
0
0
2047032
0
0
0
0
0
839808
0
0
0
0
0
0
0
0
0
0
0
0
44641044
0
20412
0
0
0
0
0
0
0
6
0
0
0
0
81
0
0
0
0
0
0
0
0
0
0
0
313155072
0
0
0
0
0
0
0
0
0
5400
0
10368
0
0
0
0
14580
0
0
0
217728
40310784
0
0
218700
0
0
0
0
1620
0
0
0
0
0
108
146304
0
0
0
466560
288
0
0
0
0
0
0
0
276138
0
0
0
0
0
0
0
52488...

result:

ok 332 tokens

Test #4:

score: 0
Accepted
time: 51ms
memory: 16024kb

input:

5
1000 0
1000 5
779 779 2
543 840 3
30 477 1
10 295 3
463 741 1
1000 6
379 569 1
249 826 2
194 819 3
90 400 1
614 808 2
102 868 2
1000 8
463 981 1
680 857 3
560 623 1
209 659 1
55 957 2
244 327 1
321 888 3
37 204 3
1000 5
336 851 3
410 676 1
522 911 2
165 962 1
258 330 3

output:

56888193
0
0
0
0

result:

ok 5 tokens

Test #5:

score: 0
Accepted
time: 48ms
memory: 16604kb

input:

5
1000 9
190 765 1
212 745 3
437 798 3
682 814 3
122 289 1
44 821 1
115 448 3
400 936 2
562 639 3
1000 5
561 808 3
23 160 2
57 915 2
211 943 3
125 596 2
1000 1
398 739 2
1000 3
629 973 2
7 721 2
591 815 2
1000 10
536 708 1
217 256 2
690 913 3
418 871 2
302 325 2
334 830 2
496 573 2
396 865 1
240 837...

output:

0
0
722271060
85306976
0

result:

ok 5 tokens

Test #6:

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

input:

2
2000 1
1501 1703 2
2000 5
1230 1521 3
1022 1939 3
1241 1283 3
767 1944 2
303 1163 3

output:

841960641
0

result:

ok 2 tokens

Test #7:

score: 0
Accepted
time: 92ms
memory: 48444kb

input:

2
2000 2
640 1942 1
1473 1917 3
2000 4
490 887 1
670 1163 3
824 1434 2
1221 1746 1

output:

0
0

result:

ok 2 tokens

Test #8:

score: 0
Accepted
time: 91ms
memory: 37156kb

input:

1
5000 9
2821 3377 2
798 1535 2
3563 4161 3
2205 2946 3
1320 1594 3
278 1624 1
1243 2759 3
2882 4939 1
2639 3559 3

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 303ms
memory: 235032kb

input:

1
5000 2
539 4252 1
906 3821 1

output:

101862333

result:

ok "101862333"

Test #10:

score: 0
Accepted
time: 3ms
memory: 4292kb

input:

111
34 0
30 0
18 0
35 0
3 0
43 0
13 0
28 0
57 0
75 0
31 0
4 0
92 0
1 0
53 0
85 0
74 0
43 0
59 0
72 0
79 0
40 0
70 0
36 0
86 0
56 0
53 0
66 0
50 0
100 0
60 0
74 0
50 0
51 0
92 0
49 0
50 0
78 0
95 0
4 0
59 0
44 0
92 0
84 0
7 0
75 0
99 0
56 0
54 0
13 0
27 0
33 0
22 0
80 0
14 0
79 0
29 0
39 0
21 0
97 0
...

output:

582926302
130653412
387420489
748778899
27
738321955
1594323
792294829
998064805
100094381
391960236
81
587240675
3
172815616
473062299
700031465
738321955
982583189
966670169
107644805
953271190
662963356
246336683
419186890
666021604
172815616
909419307
710104287
886041711
947749553
700031465
7101...

result:

ok 111 tokens

Test #11:

score: 0
Accepted
time: 20ms
memory: 6696kb

input:

16
350 0
453 0
485 0
361 0
498 0
149 0
433 0
435 0
279 0
240 0
166 0
152 0
393 0
159 0
219 0
222 0

output:

378029361
68761795
621961191
766744305
24977444
679213660
705815658
352340880
186665231
458529104
150230246
338768694
907169137
887128598
322586612
709838468

result:

ok 16 tokens

Test #12:

score: -100
Memory Limit Exceeded

input:

1
5000 0

output:

22443616

result: