Submission #1213509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213509		NAMIN	Grudanje (COCI19_grudanje)	C++20	0 / 70	2101 ms	112640 KiB

grudanje

#include <bits/stdc++.h>

#define endl "\n"
#define fast() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back

using namespace std;

int N,Q;
string s;

struct STmx{
	int len = 1;
	vector<pair<ll,ll>> tree;
	
	STmx(int l){
		while(len < l){
			len *= 2;
		}
		tree = vector<pair<ll,ll>>(len*2,{-1e9,-1e9});
	}
	
	pair<ll,ll> takeBest(pair<ll,ll> a,pair<ll,ll> b){
		/*if(a.first<a.second)
			swap(a.first,a.second);
		if(b.first<b.second)
			swap(b.first,b.second);
		if(a.second<b.first)
			swap(a.second,b.first);
		if(a.first<a.second)
			swap(a.first,a.second);
		if(b.first<b.second)
			swap(b.first,b.second);
		if(a.second<b.first)
			swap(a.second,b.first);
		if(a.first<a.second)
			swap(a.first,a.second);*/
		set<ll> s;
		s.insert(a.first);
		s.insert(a.second);
		s.insert(b.first);
		s.insert(a.second);
		vector<ll> v;
		for(auto x : s)
			v.push_back(x);
		sort(v.rbegin(),v.rend());

		return make_pair(v[0],v[1]);
	}

	void insert(int idx,int val){
		idx += len;
		tree[idx] = {val,-1e9};
		for(idx/=2;idx>=1;idx/=2){
			/*vector<ll> cur = {tree[idx*2].first,tree[idx*2].second,
								tree[idx*2+1].first,tree[idx*2+1].second};
			sort(cur.rbegin(),cur.rend());*/
			tree[idx] = takeBest(tree[idx*2],tree[idx*2+1]);
		}
	}

	pair<ll,ll> get(int l,int r){
		l += len,r += len;
		pair<ll,ll> mx = tree[l];
		while(l<=r){
			mx = takeBest(mx,tree[l]);
			mx = takeBest(mx,tree[r]);
			if(l%2==1){
				mx = takeBest(mx,tree[l++]);
			}
			if(r%2==0){
				mx = takeBest(mx,tree[r--]);
			}
			if(l<=r){
				mx = takeBest(mx,tree[l]);
				mx = takeBest(mx,tree[r]);
			}
			l/=2,r/=2;
		}
		return mx;
	}
};

void solve(){
	cin >> s;
	N = s.size();
	cin >> Q;
	vector<pair<int,int>> query;
	for(int i=0;i<Q;i++){
		int l,r;
		cin >> l >> r;
		l--,r--;
		query.pb(make_pair(l,r));
	}
	
	vector<int> p(N);
	for(int i=0;i<N;i++){
		int pos;
		cin >> pos;
		pos--;
		p[pos] = i+1;
	}

	vector<STmx> segs;
	for(int c=0;c<26;c++){
		STmx seg(N);
		for(int i=0;i<N;i++){
			if((s[i]-'a')==c){
				seg.insert(i,p[i]);
			}
		}
		segs.push_back(seg);
	}
	

	ll ans = 0;
	for(int i=0;i<Q;i++){
		int l=query[i].first,r=query[i].second;
		//cout << "lr :" << l<< ' ' << r << endl;
		for(int c=0;c<26;c++){
			//cout << c << ' ' << segs[c].get(l,r).first << ' ' << segs[c].get(l,r).second << endl;;
			ans = max(ans,segs[c].get(l,r).second);
		}
	}
	cout << ans << endl;

	//cout << segs[1].get(0,2).first << ' ' << segs[1].get(0,2).second << endl;
}

int main(){
	fast()

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 7
• Subtask 5: 0 / 7
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7