Submission #442926

#	Time	Username	Problem	Language	Result	Execution time	Memory
442926		Karliver	Grudanje (COCI19_grudanje)	C++14	70 / 70	1575 ms	94876 KiB

grudanje

	
 #include <bits/stdc++.h>
 
 #define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
 #define all(v) (v).begin(), (v).end()
 using namespace  std;
 #define forn(i,n) for (int i = 0; i < (n); ++i)
 #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
 using ll = long long;
 int mod = (ll)1e9 + 7;
 #define PI acos(-1)
 typedef pair<int, int> pairs;
 
 const int INF = 1e9 + 1;
 const int N = 2e5 + 100;
 const double eps = 1e-7;
 
 template <class T> using V = vector<T>;  
 template <class T> using VV = V<V<T>>;  
 
 template <typename XPAX>
 void ckma(XPAX &x, XPAX y) {
     x = (x < y ? y : x);
 }
 template <typename XPAX>
 void ckmi(XPAX &x, XPAX y) {
     x = (x > y ? y : x);
 }
 int l[N];
 int r[N];
 struct segT {

 	vector<pair<int, int> > ss;
 	
 	
 	int n;

 	pair<int, int> merge(pairs x, pairs y) {
 		if(x.first < y.first)swap(x, y);
 		return make_pair(x.first, max(x.second, y.first));
 	}

 	void build(V<int> & a, int p, int l, int r) {
 		if(l == r) {
 			ss[p] = {a[l - 1], -INF};
 			
 			return;
 		}
 		else {
 			int rm = (l + r) >> 1;
 			build(a, p << 1, l, rm);
 			build(a, p << 1 | 1, rm + 1, r);
 			ss[p] = merge(ss[p << 1], ss[p << 1 | 1]);
 			
 		}
 	}
 	void init(int x, V<int> & a) {
 		this-> n = x;
 		ss.resize(4 * n);
 		build(a, 1, 1, n);
 	}
 	pairs qur(int il, int ir, int p, int l, int r) {
 		if(r < il || l > ir)return {-INF, -INF};
 		if(il <= l && ir >= r) {
 			
 			return ss[p];
 		}
 		int rm =(l + r) >> 1;
 		return merge(qur(il, ir,  p << 1, l, rm), 
 		qur(il, ir,  p << 1 | 1, rm + 1, r));
 	}
 }T[26];
 void __print(int x) {cerr << x;}
 void __print(long x) {cerr << x;}
 void __print(long long x) {cerr << x;}
 void __print(unsigned x) {cerr << x;}
 void __print(unsigned long x) {cerr << x;}
 void __print(unsigned long long x) {cerr << x;}
 void __print(float x) {cerr << x;}
 void __print(double x) {cerr << x;}
 void __print(long double x) {cerr << x;}
 void __print(char x) {cerr << '\'' << x << '\'';}
 void __print(const char *x) {cerr << '\"' << x << '\"';}
 void __print(const string &x) {cerr << '\"' << x << '\"';}
 void __print(bool x) {cerr << (x ? "true" : "false");}
 
 template<typename T, typename V>
 void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
 template<typename T>
 void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
 void _print() {cerr << "]\n";}
 template <typename T, typename... V>
 void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
 #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
 void solve() {
 
 
 	
 	string s;
 	cin >> s;

 	int n = s.size();

 	

 	int q;
 	cin >> q;

 	forn(i, q) {
 		cin >> l[i] >> r[i];
 	}

 	VV<int> g(26, V<int>(n, -INF));

 	forn(pt, n) {
 		int x;
 		cin >> x;
 		--x;
 		g[s[x] - 'a'][x] = pt;
 	}

 	forn(i, 26) {
 		T[i].init(n, g[i]);
 	}
 	//debug(g[0], g[1]);
 	int ans = -INF;
 	forn(pt, q) {

 		forn(i, 26) {
 			ckma(ans, T[i].qur(l[pt], r[pt], 1, 1, n).second);
 		}
 	}

 	cout << max(0, ans + 1) << '\n';

 
 
 }
 void test_case() {
     int t;
     cin >> t;
     forn(p, t) {
 
         //cout << "Case #" << p + 1 << ": ";
         solve();
     }
 }
 int main() {
 
     ios::sync_with_stdio(false);
     cin.tie(0);
 
     solve();
 
 }
  

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