Submission #29101

#	Time	Username	Problem	Language	Result	Execution time	Memory
29101		tlwpdus	Railway Trip (JOI17_railway_trip)	C++11	45 / 100	2000 ms	57764 KiB

railway_trip

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<int,int> pii;

struct node {
	int l, r, v;
	node(int l, int r, int v):l(l),r(r),v(v){}
};

int n, k, q;
struct perstree {
	vector<node> tree;
	int init(int s=0, int e=n-1) {
		if (s==e) {
			tree.push_back(node(-1,-1,0));
			return (int)tree.size()-1;
		}
		int m = (s+e)>>1;
		tree.push_back(node(init(s,m),init(m+1,e),0));
		return (int)tree.size()-1;
	}
	int upd(int idx, int val, int ori, int s=0, int e=n-1) {
		if (e<idx||idx<s) return ori;
		if (s==e) {
			tree.push_back(tree[ori]);
			tree.back().v++;
			return (int)tree.size()-1;
		}
		int m = (s+e)>>1;
		int l = upd(idx,val,tree[ori].l,s,m), r = upd(idx,val,tree[ori].r,m+1,e);
		tree.push_back(node(l,r,tree[l].v+tree[r].v));
		return (int)tree.size()-1;
	}
	int getv(int S, int E, int cur, int s=0, int e=n-1) {
		if (e<S||E<s) return 0;
		if (S<=s&&e<=E) return tree[cur].v;
		int m = (s+e)>>1;
		return getv(S,E,tree[cur].l,s,m)+getv(S,E,tree[cur].r,m+1,e);
	}
} pst;

int l[100100], head[100100], ldx[100100];
vector<int> his[100100];
pii lis[100100][2];
set<int> s;

pii nxtl(int s, int lev) {
	if (s<0) return pii(-1,-1);
	if (l[s]>lev) return pii(0,s);
	return lis[s][0];
}

pii nxtr(int s, int lev) {
	if (s<0) return pii(-1,-1);
	if (l[s]>lev) return pii(0,s);
	return lis[s][1];
}

int dis;
pii v[5];
pii upd(pii a, int lev) {
	int i, p = 0;
	pii tmp = nxtl(a.x,lev);
	if (~tmp.second) v[p++] = tmp;
	tmp = nxtr(a.x,lev);
	if (~tmp.second) v[p++] = tmp;
	tmp = nxtl(a.y,lev);
	if (~tmp.second) v[p++] = tmp;
	tmp = nxtr(a.y,lev);
	if (~tmp.second) v[p++] = tmp;
	if (p==0) return pii(-1,-1);
	sort(v,v+p);
	int mini = v[0].first; pii res = pii(-1,-1);
	dis = mini;
	for (i=0;i<p;i++) {
		if(v[i].first==mini) {
			if (~res.first) res.second = v[i].second;
			else res.first = v[i].second;
		}
	}
	return res;
}

int psum[22][100100];
int ddd(int a, int b, int lev) {
	if (a<0||b<0) return 123456;
	if (a>b) swap(a,b);
	if (k<=20) return psum[lev][b]-psum[lev][a];
	return pst.getv(a,b,head[ldx[lev]])-1;
}
int mind(pii a, pii b, int lev) {
	return min({ddd(a.x,b.x,lev),ddd(a.y,b.x,lev),ddd(a.x,b.y,lev),ddd(a.y,b.y,lev)});
}

void ans(int s, int e) {
	if (l[s]<l[e]) swap(s,e);
	int i, dab = 0, rres = 987654321; pii a, b;
	a = pii(s,-1), b = pii(e,-1);
	for (i=l[e];i<l[s];i++) {
		dis = 0; b=upd(b,i); dab += dis;
	}
	for (i=l[s];i<k;i++) {
		rres = min(rres,dab+mind(a,b,i));
		dis = 0; a=upd(a,i); dab += dis;
		dis = 0; b=upd(b,i); dab += dis;
	}
	rres = min(rres,dab+mind(a,b,k));
	printf("%d\n",rres-1);
}

void add(int a, int b, int c, int t) {
	lis[a][t] = pii(c,b);
}
int main() {
	int i, p;

	scanf("%d%d%d",&n,&k,&q);
	for (i=0;i<n;i++) {
		scanf("%d",&l[i]); l[i]--;
		his[l[i]].push_back(i);
		lis[i][0] = lis[i][1] = pii(-1,-1);
		if (k<=20) {
			for (int j=0;j<=l[i];j++) psum[j][i]++;
		}
	}
	if (k<=20) {
		for (i=0;i<=k;i++) {
			for (int j=0;j<n;j++) psum[i][j] += ((j)?psum[i][j-1]:0);
		}
	}
	head[n] = pst.init(0,n-1); ldx[k] = n;
	p = n-1;
	for (i=k-1;i>=0;i--) {
		for (auto &v : his[i]) {
			head[p] = pst.upd(v,1,head[p+1]); p--;
		}
		ldx[i] = p+1;
		for (auto &v : his[i]) {
			auto it = s.lower_bound(v);
			if (it!=s.begin()) {--it;add(v,*it,pst.getv(*it,v,head[ldx[i]])-1,0);}
			it = s.upper_bound(v);
			if (it!=s.end()) add(v,*it,pst.getv(v,*it,head[ldx[i]])-1,1);
		}
		for (auto &v : his[i]) s.insert(v);
	}

	for (i=0;i<q;i++) {
		int a, b;
		scanf("%d%d",&a,&b); --a; --b;
		ans(a,b);
	}

    return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:121:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&k,&q);
                          ^
railway_trip.cpp:123:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&l[i]); l[i]--;
                    ^
railway_trip.cpp:153:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b); --a; --b;
                      ^

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55