Submission #334061

#	Time	Username	Problem	Language	Result	Execution time	Memory
334061		jiahng	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	767 ms	81024 KiB

sortbooks

//https://oj.uz/problem/view/IZhO19_sortbooks

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi,ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
typedef pair <pi,pi> pipi;
typedef pair <ll, pi> ipi;
#define maxn 1000001

int N, M, W[maxn];
pipi A[maxn];
int ans[maxn];
int p[maxn];

int fl(int x){
	if (p[x] == x) return p[x];
	return p[x] = fl(p[x]);
}
void join(int a,int b){
	p[fl(a)] = fl(b);
}

int main(){
	fast;
	
	cin >> N >> M;
	
	FOR(i,1,N) cin >> W[i];
	FOR(i,1,M){
		cin >> A[i].s.f >> A[i].s.s >> A[i].f.f;
		A[i].f.s = i;
	}
	
	iota(p,p+N+1,0);
	
	priority_queue <ipi,vector <ipi>, greater <ipi> > pq;
	
	FOR(i,1,N-1){
		if (W[i] > W[i + 1]) pq.push(ipi(W[i] + W[i + 1], pi(i,i + 1)));
		else join(i,i+1);
	}
	
	sort(A + 1, A + M + 1);
	
	FOR(i,1,M){
		while (!pq.empty() && pq.top().f <= A[i].f.f){
			join(pq.top().s.f, pq.top().s.s);
			pq.pop();
		}
		if (fl(A[i].s.f) == fl(A[i].s.s)) ans[A[i].f.s] = 1;
		else ans[A[i].f.s] = 0;
	}
	FOR(i,1,M) cout << ans[i] << '\n';
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23