답안 #546637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546637	2022-04-07T22:50:02 Z	inksamurai	Misspelling (JOI22_misspelling)	C++17	60 / 100	4000 ms	413236 KB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e


//snuke's mod int
template <ll mod>
struct modint{
	ll x; // typedef long long ll;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

using mint=modint<1000'000'007>;

signed main(){
_3x2WzQf;
	int n,m;
	cin>>n>>m;

	vec(vi) qry(n,vi(2,-1));
	rep(i,m){
		int l,r;
		cin>>l>>r;
		l-=1,r-=1;
		bool type=0;
		if(l>r){
			swap(l,r);
			type=1;
		}
		qry[l][type]=max(qry[l][type],r);
	}

	using tup=tuple<int,int,ll>;
	// vec(vec(vec(mint))) dp(n+1,vec(vec(mint))(27,vec(mint)(2))),ndp;
	vec(vec(mint)) dp(27,vec(mint)(2)),ndp;
	priority_queue<tup,vec(tup),greater<tup>> pq0,pq1;

	per(ch,26){
		dp[ch][0]=1;
		// pq0.push({n,});
	}
	per(i,n-1){
		ndp=dp;
		int r0=qry[i][0];
		int r1=qry[i][1];
		while(sz(pq1)){
			auto &[j,ch,val]=pq1.top();
			if(j<r0){
				ndp[ch][1]-=mint(val);
				pq1.pop();
			}else{
				break;
			}
		}
		while(sz(pq0)){
			auto &[j,ch,val]=pq0.top();
			if(j<r1){
				ndp[ch][0]-=mint(val);
				pq0.pop();
			}else{
				break;
			}
		}
		rep(x,26){
			rep(y,26){
				if(x==y) continue;
				if(r0!=-1 and y>x) continue;
				if(r1!=-1 and y<x) continue;
				rep(t,2){
					int nt=(y>x?1:0);
					ndp[y][nt]+=dp[x][t];
					if(nt) pq1.push({i,y,dp[x][t].x});
					else pq0.push({i,y,dp[x][t].x});
				}
			}
		}
		dp.swap(ndp);
	}

	mint ans=0;
	rep(x,26){
		rep(t,2){
			ans+=dp[x][t];
		}
	}

	print(ans.x);
//	
	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	15 ms	2760 KB	Output is correct
16	Correct	23 ms	1556 KB	Output is correct
17	Correct	23 ms	976 KB	Output is correct
18	Correct	23 ms	724 KB	Output is correct
19	Correct	20 ms	724 KB	Output is correct
20	Correct	19 ms	672 KB	Output is correct
21	Correct	27 ms	1168 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	22 ms	4428 KB	Output is correct
24	Correct	29 ms	1232 KB	Output is correct
25	Correct	16 ms	596 KB	Output is correct

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Execution timed out	4025 ms	28864 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	15 ms	2760 KB	Output is correct
16	Correct	23 ms	1556 KB	Output is correct
17	Correct	23 ms	976 KB	Output is correct
18	Correct	23 ms	724 KB	Output is correct
19	Correct	20 ms	724 KB	Output is correct
20	Correct	19 ms	672 KB	Output is correct
21	Correct	27 ms	1168 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	22 ms	4428 KB	Output is correct
24	Correct	29 ms	1232 KB	Output is correct
25	Correct	16 ms	596 KB	Output is correct
26	Correct	1593 ms	1940 KB	Output is correct
27	Correct	1342 ms	265584 KB	Output is correct
28	Correct	1427 ms	267360 KB	Output is correct
29	Correct	2041 ms	34432 KB	Output is correct
30	Correct	2037 ms	34412 KB	Output is correct
31	Correct	1094 ms	34460 KB	Output is correct
32	Correct	1802 ms	2200 KB	Output is correct
33	Correct	1751 ms	1972 KB	Output is correct
34	Correct	2345 ms	6668 KB	Output is correct
35	Correct	235 ms	2308 KB	Output is correct
36	Correct	1293 ms	413236 KB	Output is correct
37	Correct	2504 ms	8132 KB	Output is correct
38	Correct	2910 ms	8844 KB	Output is correct
39	Correct	3402 ms	23180 KB	Output is correct

Subtask #5
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	15 ms	2760 KB	Output is correct
16	Correct	23 ms	1556 KB	Output is correct
17	Correct	23 ms	976 KB	Output is correct
18	Correct	23 ms	724 KB	Output is correct
19	Correct	20 ms	724 KB	Output is correct
20	Correct	19 ms	672 KB	Output is correct
21	Correct	27 ms	1168 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	22 ms	4428 KB	Output is correct
24	Correct	29 ms	1232 KB	Output is correct
25	Correct	16 ms	596 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Execution timed out	4025 ms	28864 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

답안 #546637

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 29.0

Subtask #4 32.0 / 32.0

Subtask #5 0 / 11.0

Subtask #1
8.0 / 8.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 29.0

Subtask #4
32.0 / 32.0

Subtask #5
0 / 11.0