Submission #785045

#	Time	Username	Problem	Language	Result	Execution time	Memory
785045		tolbi	Toll (BOI17_toll)	C++17	100 / 100	119 ms	13268 KiB

toll

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
#ifdef tolbi
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<"{ "<<pr.first<<", "<<pr.second<<" }";}
#else
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
#endif
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
template<typename X> istream& operator>>(istream& is, vector<X> &arr){for (auto &it : arr) is>>it; return is;}
template<typename X, size_t Y> istream& operator>>(istream& is, array<X,Y> &arr){for (auto &it : arr) is>>it; return is;}
template<typename X> ostream& operator<<(ostream& os, vector<X> &arr){for (auto &it : arr) os<<" "<<it;os<<endl;return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> &arr){for (auto &it : arr) os<<" "<<it;os<<endl;return os;}
#define int long long
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = LONG_LONG_MAX;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
vector<vector<vector<int>>> segtree;
vector<vector<int>> bos;
vector<vector<int>> neg;
int k;
void merge(int node){
	int left = node*2+1;
	int right = node*2+2;
	for (int i = 0; i < k; i++){
		for (int j = 0; j < k; j++){
			for (int z = 0; z < k; z++){
				if (segtree[left][i][z]==-1 || segtree[right][z][j]==-1) continue;
				int crr = segtree[left][i][z]+segtree[right][z][j];
				if (segtree[node][i][j]==-1){
					segtree[node][i][j]=crr;
				}
				else {
					segtree[node][i][j]=min(segtree[node][i][j],crr);
				}
			}
		}
	}
}
vector<vector<int>> query(int tarl, int tarr, int l = 0, int r = segtree.size()/2, int node = 0){
	if (l>=tarl && r<=tarr) return segtree[node];
	if (l>tarr || r<tarl) return bos;
	int mid = l+(r-l)/2;
	vector<vector<int>> lnode = query(tarl, tarr, l, mid, node*2+1);
	vector<vector<int>> rnode = query(tarl, tarr, mid+1, r, node*2+2);
	vector<vector<int>> res = neg;
	if (lnode[0][0]==-2) return rnode;
	if (rnode[0][0]==-2) return lnode;
	for (int i = 0; i < k; i++){
		for (int j = 0; j < k; j++){
			for (int z = 0; z < k; z++){
				if (lnode[i][z]==-1 || rnode[z][j]==-1) continue;
				int crr = lnode[i][z]+rnode[z][j];
				if (res[i][j]==-1){
					res[i][j]=crr;
				}
				else {
					res[i][j]=min(res[i][j],crr);
				}
			}
		}
	}
	return res;
}
//update olsa onu da yaparduk da soru fazla kolay lol
int32_t main(){
	ios;
	int T = 1;
	if (!T) cin>>T;
	int tno = 0;
	while (T-(tno++)){
		cin>>k;deci(n);deci(m);deci(q);
		segtree.resize(tol(ceil(log2((n+k-1)/k)+1))-1,vector<vector<int>>(k,vector<int>(k,-1)));
		bos.resize(k,vector<int>(k,-2));
		neg.resize(k,vector<int>(k,-1));
		for (int i = 0; i < m; ++i)
		{
			deci(a);deci(b);deci(x);
			segtree[a/k+segtree.size()/2][a%k][b%k]=x;
		}
		for (int i = segtree.size()/2-1; i >= 0; i--){
			merge(i);
		}
		while (q--){
			deci(a);deci(b);
			if (a==b){
				cout<<0<<endl;
				continue;
			}
			if (b/k<=a/k){
				cout<<-1<<endl;
				continue;
			}
			vector<vector<int>> res = query(a/k,b/k-1);
			if (res[a%k][b%k]==-1){
				cout<<-1<<endl;
			}
			else {
				cout<<res[a%k][b%k]<<endl;
			}
		}
	}
}

Compilation message (stderr)

toll.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44