oj.uz

Submission #27492

# Submission time Handle Problem Language Result Execution time Memory
27492 2017-07-13T07:48:41 Z 시제연(#1156) OGLEDALA (COI15_ogledala) C++
41 / 100
 4000 ms 83356 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

struct lin {
	ll len, num;
	int idx;
	lin(ll l, int i, ll n):len(l),idx(i),num(n){}
	bool operator < (const lin &A) const {
		return len!=A.len?len<A.len:idx>A.idx;
	}
	bool operator == (const lin &A) const {
		return len==A.len&&idx==A.idx;
	}
};
void operator += (lin &A, const lin &B) {
	A.num += B.num;
}

map<pll,ll> gt;

ll g(ll n, ll k) {
	if (gt.find(pll(n,k))!=gt.end()) return gt[pll(n,k)];
	if (n<=k) return (n==k);
	return (gt[pll(n,k)] = g(n-1-n/2,k)+g(n/2,k));
}

ll f(ll n, ll k, ll t) {
	if (n==k) return (n-1)/2;
	ll v = g(n-1-n/2,k);
	return (v>=t?f(n-1-n/2,k,t):(n+1)/2+f(n/2,k,t-v));
}

ll m, n, q;
ll a[100100];

priority_queue<lin> pq;
vector<ll> que;

int main() {
	int i;

	scanf("%lld%lld%lld",&m,&n,&q);
	for (i=1;i<=n;i++) {
		scanf("%lld",&a[i]); a[i]--;
	}
	a[0] = -1; a[n+1] = m;
	for (i=1;i<=n+1;i++) {
		if (a[i]-a[i-1]==1) continue;
		pq.push(lin(a[i]-a[i-1]-1,i,1));
	}
	for (i=0;i<q;i++) {
		ll v;
		scanf("%lld",&v);
		if (v<=n) printf("%lld\n",a[v]+1);
		else que.push_back(v);
	}
	ll cnt = n; int p = 0;
	while(!pq.empty()) {
		lin tmp = pq.top();
		pq.pop();
		while(!pq.empty()&&pq.top()==tmp) {
			tmp += pq.top();
			pq.pop();
		}
		while(p<que.size()&&que[p]<=cnt+tmp.num) {
			printf("%lld\n",f(a[tmp.idx]-a[tmp.idx-1]-1,tmp.len,que[p]-cnt)+a[tmp.idx-1]+2); p++;
		}
		if (p==que.size()) break;
		pq.push(lin(tmp.len-1-tmp.len/2,tmp.idx,tmp.num));
		pq.push(lin(tmp.len/2,tmp.idx,tmp.num));
		cnt += tmp.num;
	}

    return 0;
}

Compilation message

ogledala.cpp: In constructor 'lin::lin(ll, int, ll)':
ogledala.cpp:10:6: warning: 'lin::idx' will be initialized after [-Wreorder]
  int idx;
      ^
ogledala.cpp:9:10: warning:   'll lin::num' [-Wreorder]
  ll len, num;
          ^
ogledala.cpp:11:2: warning:   when initialized here [-Wreorder]
  lin(ll l, int i, ll n):len(l),idx(i),num(n){}
  ^
ogledala.cpp: In function 'int main()':
ogledala.cpp:69:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p<que.size()&&que[p]<=cnt+tmp.num) {
          ^
ogledala.cpp:72:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (p==que.size()) break;
        ^
ogledala.cpp:46:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&m,&n,&q);
                                ^
ogledala.cpp:48:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]); a[i]--;
                      ^
ogledala.cpp:57:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&v);
                   ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2808 KB Output is correct
2 Correct 0 ms 2808 KB Output is correct
3 Correct 53 ms 5204 KB Output is correct
4 Correct 43 ms 5204 KB Output is correct
5 Correct 123 ms 14160 KB Output is correct
6 Correct 156 ms 14160 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3480 KB Output is correct
2 Correct 6 ms 3616 KB Output is correct
3 Correct 196 ms 13136 KB Output is correct
4 Correct 116 ms 13136 KB Output is correct
5 Correct 163 ms 14160 KB Output is correct
6 Correct 213 ms 14160 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 3716 ms 37552 KB Output is correct
2 Correct 3703 ms 35312 KB Output is correct
3 Execution timed out 4000 ms 83356 KB Execution timed out
4 Halted 0 ms 0 KB -