Submission #857110

#	Time	Username	Problem	Language	Result	Execution time	Memory
857110		Onur_Ilgaz	OGLEDALA (COI15_ogledala)	C++17	19 / 100	1270 ms	524288 KiB

ogledala

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
int m, n, q;
vector <int> points, interval;
vector <int> ufound, found;
vector <int> numbers;
vector <vector<pair<int, int> > > dp, sayi; // [numberindex][nomeaning]
											// {includesthisindex, with this freq}

void findnumbers(int x) {
	if(x == 0) return;
	int x1 = x, x2 = x;
	while(x1 or x2) {
		if(x1) found.push_back(x1);
		if(x2) found.push_back(x2);
		int f = (x1 - 1) / 2, s = x1 / 2, ff = (x2 - 1) / 2, ss = x2 / 2;
		set <int> st;
		st.insert(f);
		st.insert(s);
		st.insert(ff);
		st.insert(ss);
		vector <int> bro;
		for(auto it:st) {
			bro.push_back(it);
		}
		bro.push_back(bro[0]);
		x1 = bro[0], x2 = bro[1];
	}
}

int find(int x) {
	return (lower_bound(numbers.begin(), numbers.end(), x) - numbers.begin());
}

int finding(int dpindex, int search) {
	int l = 0, r = dp[dpindex].size();
	while(r - l > 1) {
		int m = (r + l) / 2;
		if(dp[dpindex][m].first > search) {
			r = m;
		}
		else {
			l = m;
		}
	}
	return l;
}

void calc(int numindex) {
	int x = numbers[numindex];
	int f = (x - 1) / 2, s = x / 2;
	if(x == 2) {
		dp[numindex] = dp[find(f)];
	}
	if(x <= 2) {
		dp[numindex].push_back({numindex, 1});
		return;
	}
	if(x % 2) {
		for(auto &[index, val]:dp[find(f)]) {
			dp[numindex].push_back({index, val * 2});
		}
	}
	else {
		vector <pair<int, int> > tempv = dp[find(f)];
		for(auto &[index, val]:dp[find(s)]) {
			tempv.push_back({index, val});
		}
		sort(tempv.begin(), tempv.end());
		for(int i = 0; i < tempv.size(); i++){
			int val = tempv[i].second;
			if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
				val += tempv[i + 1].second;
				i++;
			}	
			dp[numindex].push_back({tempv[i].first, val});
		}
	}
	dp[numindex].push_back({numindex, 1});
}

int32_t main(){
	fast
	cin>>m>>n>>q;
	points.push_back(0);
	for(int i = 1; i <= n; i++) {
		int in;
		cin>>in;
		points.push_back(in);
	}
	points.push_back(m + 1);
	for(int i = 0; i <= n; i++) {
		interval.push_back(points[i + 1] - points[i] - 1);
		findnumbers(interval[i]);
	}
	sort(found.begin(), found.end());
	found.push_back(inf);
	for(int i = 0; i < found.size() - 1; i++) {
		if(found[i] != found[i+1]) {
			ufound.push_back(found[i]);
		}
	}
	dp.resize(ufound.size());
	sayi.resize(ufound.size());
	for(auto it:ufound) {
		// cout<<it<<" ";
		numbers.push_back(it);
		calc(numbers.size() - 1);
	}
	for(int i = 0; i <= n; i++) {
		int st = points[i], length = interval[i];
		if(length == 0) continue;
		for(auto &[index, freq]:dp[find(length)]) {
			sayi[index].push_back({i, freq});
		}
	}
	int allindex = numbers.size() - 1, sayindex = 0, gone = 0; 
	for(int i = 0; i < q; i++) {
		int query;
		cin>>query;
		if(query <= n) {
			cout<<points[query]<<"\n";
			continue;
		}
		query -= n;
		int rem = query - gone, val;
		while(true) {
			val = sayi[allindex][sayindex].second;
			if(val >= rem) break;
			gone += val;
			rem -= val;
			sayindex++;
			if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
		}
		int intervalIndex = sayi[allindex][sayindex].first;
		// use rem to navigate inside the interval
		val = interval[intervalIndex];
		int stpoint = points[intervalIndex];
		int add = 0;
		// allindexe göre searchla
		// cout<<numbers[allindex]<<":\n";
		while(val > numbers[allindex]) {
			// cout<<val<<" "<<add<<" "<<rem<<"\n";
			int f = (val - 1) / 2, s = val / 2;
			int findex = find(f);
			int underindex = finding(findex, allindex);
			if(!f or dp[findex][underindex].first != allindex) {
				// cout<<"right1\n";
				add += f + 1;
				val = s;
				continue;
			}
			int leftfreq = dp[findex][underindex].second;
			if(leftfreq >= rem) {
				// cout<<"left\n";
				val = f;
			}
			else {
				// cout<<"right\n";
				add += f + 1;
				rem -= leftfreq;
				val = s;
			}
		}
		// cout<<val<<"\n";
		add += (val - 1) / 2;
		cout<<add + stpoint + 1<<"\n";
	}
	cerr<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds\n";
}

Compilation message (stderr)

ogledala.cpp: In function 'void calc(long long int)':
ogledala.cpp:74:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i = 0; i < tempv.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
ogledala.cpp:76:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
      |       ~~^~~~~~~~~~~~~~~~~~
ogledala.cpp: In function 'int32_t main()':
ogledala.cpp:102:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i < found.size() - 1; i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
ogledala.cpp:115:7: warning: unused variable 'st' [-Wunused-variable]
  115 |   int st = points[i], length = interval[i];
      |       ^~
ogledala.cpp:137:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
      |       ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59