oj.uz

Submission #419720

# Submission time Handle Problem Language Result Execution time Memory
419720 2021-06-07T11:55:23 Z zaneyu Crossing (JOI21_crossing) C++14
100 / 100
 2781 ms 17728 KB 
/*input
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (ll)x.size()
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e17;
const int INF=0x3f3f3f3f;
const ll MOD=3006703054056749LL;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
	ll res=0;
	while(b){
		if(b&1) res+=a,res%=MOD;
		a+=a;
		a%=MOD; 
		b>>=1;
	}
	return res;
}
ll mypow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=mult(res,a);
		a=mult(a,a);
		b/=2;
	}
	return res;
}
#define int ll
int pww[maxn];
string arr[3];
string bl="JOI";
string op(string a,string b){
	string ans="";
	REP(i,sz(a)){
		if(a[i]==b[i]) ans.pb(a[i]);
		else{
			REP(k,3){
				if(bl[k]!=a[i] and bl[k]!=b[i]) ans.pb(bl[k]);
			}
		}
	}
	return ans;
}
struct node{
	ll sum=0,lazy=0,len=0;
}seg[4*maxn];
ll pf[maxn];
void build(int idx,int l,int r){
	seg[idx].len=(r-l+1);
	if(l==r) return;
	int mid=(l+r)/2;
	build(idx*2,l,mid);
	build(idx*2+1,mid+1,r);
}
void pushdown(int idx,int l,int r){
	if(seg[idx].lazy==0) return;
	seg[idx].sum=mult(pf[seg[idx].len-1],seg[idx].lazy);
	if(l!=r){
		seg[idx*2].lazy=seg[idx].lazy;
		seg[idx*2+1].lazy=seg[idx].lazy;
	}
	seg[idx].lazy=0;
}
node merge(node a,node b){
	node c;
	c.sum=(a.sum+mult(b.sum,pww[a.len]))%MOD;
	c.len=a.len+b.len;
	return c;
}
void upd(int idx,int l,int r,int ql,int qr,int x){
	pushdown(idx,l,r);
	if(r<ql or l>qr) return;
	if(ql<=l and r<=qr){
		seg[idx].lazy=x;
		pushdown(idx,l,r);
		return;
	}
	int mid=(l+r)/2;
	upd(idx*2,l,mid,ql,qr,x);
	upd(idx*2+1,mid+1,r,ql,qr,x);
	seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
}
map<char,int> mp;
int hsh(string s){
	int pw=1;
	ll ans=0;
	for(auto x:s){
		ans+=mult(pw,mp[x]);
		ans%=MOD;
		pw=mult(pw,4);
	}
	return ans;
}
int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int n;
	cin>>n;
	REP(i,3) cin>>arr[i];
	mp['J']=1,mp['O']=2,mp['I']=3;
	vector<string> v;
	map<int,int> cnt;
	REP(i,3){
		cnt[hsh(arr[i])]++;
		REP(j,i){
			string z=op(arr[i],arr[j]);
			cnt[hsh(z)]++;
		}
	}
	pww[0]=pf[0]=1;
	REP1(i,n) pww[i]=mult(pww[i-1],4),pf[i]=(pf[i-1]+pww[i])%MOD;
	vector<int> b;
	REP(i,3) b.pb(i);
	do{
		string cur="";
		for(auto x:b){
			if(!sz(cur)) cur=arr[x];
			else cur=op(cur,arr[x]);
		}
		cnt[hsh(cur)]++;
	}while(next_permutation(ALL(b)));
	int q;
	string s;
	cin>>q>>s;
	build(1,0,n-1);
	REP(i,n) upd(1,0,n-1,i,i,mp[s[i]]);
	if(cnt.count(seg[1].sum)){
		cout<<"Yes\n";
	}
	else cout<<"No\n";
	while(q--){
		int l,r;
		char c;
		cin>>l>>r>>c;
		--l,--r;
		upd(1,0,n-1,l,r,mp[c]);
		if(cnt.count(seg[1].sum)){
			cout<<"Yes\n";
		}
		else cout<<"No\n";
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 836 KB Output is correct
2 Correct 288 ms 836 KB Output is correct
3 Correct 357 ms 836 KB Output is correct
4 Correct 235 ms 908 KB Output is correct
5 Correct 241 ms 864 KB Output is correct
6 Correct 237 ms 868 KB Output is correct
7 Correct 223 ms 868 KB Output is correct
8 Correct 250 ms 916 KB Output is correct
9 Correct 253 ms 832 KB Output is correct
10 Correct 253 ms 892 KB Output is correct
11 Correct 255 ms 964 KB Output is correct
12 Correct 252 ms 944 KB Output is correct
13 Correct 252 ms 880 KB Output is correct
14 Correct 253 ms 912 KB Output is correct
15 Correct 284 ms 888 KB Output is correct
16 Correct 252 ms 920 KB Output is correct
17 Correct 259 ms 888 KB Output is correct
18 Correct 282 ms 1016 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 836 KB Output is correct
2 Correct 288 ms 836 KB Output is correct
3 Correct 357 ms 836 KB Output is correct
4 Correct 235 ms 908 KB Output is correct
5 Correct 241 ms 864 KB Output is correct
6 Correct 237 ms 868 KB Output is correct
7 Correct 223 ms 868 KB Output is correct
8 Correct 250 ms 916 KB Output is correct
9 Correct 253 ms 832 KB Output is correct
10 Correct 253 ms 892 KB Output is correct
11 Correct 255 ms 964 KB Output is correct
12 Correct 252 ms 944 KB Output is correct
13 Correct 252 ms 880 KB Output is correct
14 Correct 253 ms 912 KB Output is correct
15 Correct 284 ms 888 KB Output is correct
16 Correct 252 ms 920 KB Output is correct
17 Correct 259 ms 888 KB Output is correct
18 Correct 282 ms 1016 KB Output is correct
19 Correct 2482 ms 17500 KB Output is correct
20 Correct 2705 ms 17532 KB Output is correct
21 Correct 1788 ms 17396 KB Output is correct
22 Correct 1621 ms 16956 KB Output is correct
23 Correct 728 ms 1988 KB Output is correct
24 Correct 714 ms 1944 KB Output is correct
25 Correct 1872 ms 17712 KB Output is correct
26 Correct 1816 ms 17608 KB Output is correct
27 Correct 2100 ms 17588 KB Output is correct
28 Correct 2090 ms 17504 KB Output is correct
29 Correct 2081 ms 17268 KB Output is correct
30 Correct 804 ms 1936 KB Output is correct
31 Correct 2074 ms 17596 KB Output is correct
32 Correct 1882 ms 17484 KB Output is correct
33 Correct 723 ms 1868 KB Output is correct
34 Correct 2021 ms 17592 KB Output is correct
35 Correct 1500 ms 16340 KB Output is correct
36 Correct 715 ms 1852 KB Output is correct
37 Correct 732 ms 1880 KB Output is correct
38 Correct 2279 ms 17564 KB Output is correct
39 Correct 1817 ms 17540 KB Output is correct
40 Correct 1494 ms 9916 KB Output is correct
41 Correct 2485 ms 17728 KB Output is correct
42 Correct 875 ms 17712 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 836 KB Output is correct
2 Correct 288 ms 836 KB Output is correct
3 Correct 357 ms 836 KB Output is correct
4 Correct 235 ms 908 KB Output is correct
5 Correct 241 ms 864 KB Output is correct
6 Correct 237 ms 868 KB Output is correct
7 Correct 223 ms 868 KB Output is correct
8 Correct 250 ms 916 KB Output is correct
9 Correct 253 ms 832 KB Output is correct
10 Correct 253 ms 892 KB Output is correct
11 Correct 255 ms 964 KB Output is correct
12 Correct 252 ms 944 KB Output is correct
13 Correct 252 ms 880 KB Output is correct
14 Correct 253 ms 912 KB Output is correct
15 Correct 284 ms 888 KB Output is correct
16 Correct 252 ms 920 KB Output is correct
17 Correct 259 ms 888 KB Output is correct
18 Correct 282 ms 1016 KB Output is correct
19 Correct 283 ms 808 KB Output is correct
20 Correct 337 ms 1020 KB Output is correct
21 Correct 246 ms 836 KB Output is correct
22 Correct 217 ms 764 KB Output is correct
23 Correct 263 ms 868 KB Output is correct
24 Correct 229 ms 844 KB Output is correct
25 Correct 289 ms 940 KB Output is correct
26 Correct 213 ms 884 KB Output is correct
27 Correct 262 ms 920 KB Output is correct
28 Correct 225 ms 864 KB Output is correct
29 Correct 249 ms 908 KB Output is correct
30 Correct 195 ms 864 KB Output is correct
31 Correct 270 ms 864 KB Output is correct
32 Correct 252 ms 844 KB Output is correct
33 Correct 256 ms 856 KB Output is correct
34 Correct 215 ms 888 KB Output is correct
35 Correct 251 ms 836 KB Output is correct
36 Correct 270 ms 904 KB Output is correct
37 Correct 255 ms 876 KB Output is correct
38 Correct 283 ms 896 KB Output is correct
39 Correct 257 ms 928 KB Output is correct
40 Correct 281 ms 828 KB Output is correct
41 Correct 257 ms 836 KB Output is correct
42 Correct 260 ms 816 KB Output is correct
43 Correct 232 ms 804 KB Output is correct
44 Correct 287 ms 868 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 836 KB Output is correct
2 Correct 288 ms 836 KB Output is correct
3 Correct 357 ms 836 KB Output is correct
4 Correct 235 ms 908 KB Output is correct
5 Correct 241 ms 864 KB Output is correct
6 Correct 237 ms 868 KB Output is correct
7 Correct 223 ms 868 KB Output is correct
8 Correct 250 ms 916 KB Output is correct
9 Correct 253 ms 832 KB Output is correct
10 Correct 253 ms 892 KB Output is correct
11 Correct 255 ms 964 KB Output is correct
12 Correct 252 ms 944 KB Output is correct
13 Correct 252 ms 880 KB Output is correct
14 Correct 253 ms 912 KB Output is correct
15 Correct 284 ms 888 KB Output is correct
16 Correct 252 ms 920 KB Output is correct
17 Correct 259 ms 888 KB Output is correct
18 Correct 282 ms 1016 KB Output is correct
19 Correct 2482 ms 17500 KB Output is correct
20 Correct 2705 ms 17532 KB Output is correct
21 Correct 1788 ms 17396 KB Output is correct
22 Correct 1621 ms 16956 KB Output is correct
23 Correct 728 ms 1988 KB Output is correct
24 Correct 714 ms 1944 KB Output is correct
25 Correct 1872 ms 17712 KB Output is correct
26 Correct 1816 ms 17608 KB Output is correct
27 Correct 2100 ms 17588 KB Output is correct
28 Correct 2090 ms 17504 KB Output is correct
29 Correct 2081 ms 17268 KB Output is correct
30 Correct 804 ms 1936 KB Output is correct
31 Correct 2074 ms 17596 KB Output is correct
32 Correct 1882 ms 17484 KB Output is correct
33 Correct 723 ms 1868 KB Output is correct
34 Correct 2021 ms 17592 KB Output is correct
35 Correct 1500 ms 16340 KB Output is correct
36 Correct 715 ms 1852 KB Output is correct
37 Correct 732 ms 1880 KB Output is correct
38 Correct 2279 ms 17564 KB Output is correct
39 Correct 1817 ms 17540 KB Output is correct
40 Correct 1494 ms 9916 KB Output is correct
41 Correct 2485 ms 17728 KB Output is correct
42 Correct 875 ms 17712 KB Output is correct
43 Correct 283 ms 808 KB Output is correct
44 Correct 337 ms 1020 KB Output is correct
45 Correct 246 ms 836 KB Output is correct
46 Correct 217 ms 764 KB Output is correct
47 Correct 263 ms 868 KB Output is correct
48 Correct 229 ms 844 KB Output is correct
49 Correct 289 ms 940 KB Output is correct
50 Correct 213 ms 884 KB Output is correct
51 Correct 262 ms 920 KB Output is correct
52 Correct 225 ms 864 KB Output is correct
53 Correct 249 ms 908 KB Output is correct
54 Correct 195 ms 864 KB Output is correct
55 Correct 270 ms 864 KB Output is correct
56 Correct 252 ms 844 KB Output is correct
57 Correct 256 ms 856 KB Output is correct
58 Correct 215 ms 888 KB Output is correct
59 Correct 251 ms 836 KB Output is correct
60 Correct 270 ms 904 KB Output is correct
61 Correct 255 ms 876 KB Output is correct
62 Correct 283 ms 896 KB Output is correct
63 Correct 257 ms 928 KB Output is correct
64 Correct 281 ms 828 KB Output is correct
65 Correct 257 ms 836 KB Output is correct
66 Correct 260 ms 816 KB Output is correct
67 Correct 232 ms 804 KB Output is correct
68 Correct 287 ms 868 KB Output is correct
69 Correct 2102 ms 16724 KB Output is correct
70 Correct 2781 ms 17512 KB Output is correct
71 Correct 747 ms 1936 KB Output is correct
72 Correct 807 ms 1908 KB Output is correct
73 Correct 787 ms 1948 KB Output is correct
74 Correct 1750 ms 16792 KB Output is correct
75 Correct 736 ms 1892 KB Output is correct
76 Correct 1983 ms 17540 KB Output is correct
77 Correct 1700 ms 16768 KB Output is correct
78 Correct 713 ms 2032 KB Output is correct
79 Correct 745 ms 1916 KB Output is correct
80 Correct 1530 ms 16200 KB Output is correct
81 Correct 743 ms 1888 KB Output is correct
82 Correct 1916 ms 17512 KB Output is correct
83 Correct 1807 ms 17216 KB Output is correct
84 Correct 739 ms 1908 KB Output is correct
85 Correct 718 ms 1892 KB Output is correct
86 Correct 1794 ms 16460 KB Output is correct
87 Correct 2076 ms 17508 KB Output is correct
88 Correct 793 ms 1952 KB Output is correct
89 Correct 1844 ms 16984 KB Output is correct
90 Correct 2066 ms 17636 KB Output is correct
91 Correct 769 ms 1876 KB Output is correct
92 Correct 1605 ms 16412 KB Output is correct
93 Correct 715 ms 1920 KB Output is correct
94 Correct 703 ms 1932 KB Output is correct
95 Correct 720 ms 1956 KB Output is correct
96 Correct 2219 ms 17672 KB Output is correct
97 Correct 1830 ms 17552 KB Output is correct
98 Correct 1512 ms 9928 KB Output is correct
99 Correct 2582 ms 17636 KB Output is correct
100 Correct 944 ms 17712 KB Output is correct