oj.uz

Submission #29090

# Submission time Handle Problem Language Result Execution time Memory
29090 2017-07-18T08:36:00 Z 시제연(#1172) Railway Trip (JOI17_railway_trip) C++11
20 / 100
 2000 ms 49164 KB 
#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 ddd(int a, int b, int lev) {
	if (a>b) swap(a,b);
	if (a<0||b<0) return 123456;
	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);
	}
	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

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:119: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:121: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:143: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7132 KB Output is correct
2 Correct 0 ms 7132 KB Output is correct
3 Correct 0 ms 7132 KB Output is correct
4 Correct 0 ms 7132 KB Output is correct
5 Correct 0 ms 7132 KB Output is correct
6 Correct 0 ms 7132 KB Output is correct
7 Correct 0 ms 7132 KB Output is correct
8 Correct 0 ms 7132 KB Output is correct
9 Correct 0 ms 7132 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7616 KB Output is correct
2 Correct 166 ms 46528 KB Output is correct
3 Correct 249 ms 46764 KB Output is correct
4 Correct 266 ms 46600 KB Output is correct
5 Correct 279 ms 46752 KB Output is correct
6 Correct 306 ms 46768 KB Output is correct
7 Correct 1706 ms 48312 KB Output is correct
8 Correct 1293 ms 44980 KB Output is correct
9 Correct 453 ms 47364 KB Output is correct
10 Correct 456 ms 47172 KB Output is correct
11 Correct 526 ms 47484 KB Output is correct
12 Correct 479 ms 47260 KB Output is correct
13 Correct 429 ms 47176 KB Output is correct
14 Correct 656 ms 47484 KB Output is correct
15 Correct 393 ms 47256 KB Output is correct
16 Correct 463 ms 47172 KB Output is correct
17 Correct 119 ms 46576 KB Output is correct
18 Correct 163 ms 46500 KB Output is correct
19 Correct 1746 ms 49164 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 46444 KB Output is correct
2 Correct 896 ms 46492 KB Output is correct
3 Correct 1299 ms 46748 KB Output is correct
4 Correct 1259 ms 46524 KB Output is correct
5 Correct 1363 ms 46820 KB Output is correct
6 Correct 1649 ms 46796 KB Output is correct
7 Correct 1549 ms 46788 KB Output is correct
8 Correct 413 ms 44600 KB Output is correct
9 Correct 716 ms 44980 KB Output is correct
10 Correct 946 ms 44980 KB Output is correct
11 Correct 796 ms 44980 KB Output is correct
12 Correct 929 ms 44980 KB Output is correct
13 Correct 1039 ms 44980 KB Output is correct
14 Execution timed out 2000 ms 44984 KB Execution timed out
15 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 48300 KB Execution timed out
2 Halted 0 ms 0 KB -