oj.uz

Submission #240272

# Submission time Handle Problem Language Result Execution time Memory
240272 2020-06-19T06:04:27 Z frodakcin Fortune Telling 2 (JOI14_fortune_telling2) C++11
4 / 100
 31 ms 6396 KB 
#include <cstdio>
#include <cstring>
//#define NDEBUG
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>

using ll = long long;
const int MN = 2e5+10, MK = 2e5+10, MV = MN*2+MK, MX = 1.5e5;//MX = 1.5e7

int s[MX], c[MX][2], X=1, v[MV], V, a[MN], b[MN], t[MK], N, K, n[MV], r[MN];
struct evt{public:int v, id;bool operator < (evt o)const{return v>o.v;}};//reversed sort
std::vector<evt> q;
ll f;

int upd(int n, int l, int r, int q, int v)
{
	++X;
	assert(X<MX);
	if(n)
	{
		memcpy(c[X], c[n], 8);
		s[X]=s[n];
	}
	n=X;
	s[n]+=v;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(q<m) c[n][0]=upd(c[n][0], l, m, q, v);
		else c[n][1]=upd(c[n][1], m, r, q, v);
		assert(s[n] == s[c[n][0]] + s[c[n][1]]);
	}
	return n;
}
int diff(int n, int u, int l, int r)
{
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(s[c[n][1]] != s[c[u][1]]) return diff(c[n][1], c[u][1], m, r);
		else return diff(c[n][0], c[u][0], l, m);
	}
	else
		return l;
}
int qry(int n, int l, int r, int ql, int qr)
{
	if(!n) return 0;
	if(ql <= l&&r <= qr) return s[n];
	else
	{
		int m=l+(r-l)/2, f=0;
		if(ql<m) f+=qry(c[n][0], l, m, ql, qr);
		if(m<qr) f+=qry(c[n][1], m, r, ql, qr);
		return f;
	}
}
int main()
{
	scanf("%d%d", &N, &K);
	for(int i=0;i<N;++i)
	{
		scanf("%d", a+i), v[V++]=a[i];
		scanf("%d", b+i), v[V++]=b[i];
	}
	for(int i=0;i<K;++i) scanf("%d", t+i), v[V++]=t[i];
	std::sort(v, v+V);
	V = std::unique(v, v+V)-v;
	//for(int i=0;i<V;++i) printf("%d%c", v[i], " \n"[i+1==V]);
	for(int i=0;i<K;++i)
		t[i]=std::lower_bound(v, v+V, t[i])-v, q.push_back({t[i], i});
	std::sort(q.begin(), q.end());
	r[V]=1;
	for(int i=V-1,j=0;i>=0;--i)
	{
		r[i]=r[i+1];
		for(;j<K&&q[j].v==i;++j)//greater or equ
			r[i] = upd(r[i], 0, K, q[j].id, 1);
		//printf("NUM: %d: %d\n", v[i], s[r[i]]);
	}
	for(int i=0;i<N;++i)
	{
		a[i]=std::lower_bound(v, v+V, a[i])-v;
		b[i]=std::lower_bound(v, v+V, b[i])-v;
		//printf("TESTALL(%d,%d): %d %d\n", v[a[i]], v[b[i]], s[r[a[i]]], s[r[b[i]]]);
		if(s[r[a[i]]] == s[r[b[i]]])
			if(s[r[a[i]]]&1)
				f+=v[b[i]];
			else
				f+=v[a[i]];
		else
		{
			assert(a[i]!=b[i]);
			int t=diff(r[a[i]], r[b[i]], 0, K), u=t+1<K?qry(r[a[i]], 0, K, t+1, K):0;//for finding u, result should be same for r[a[i]] and r[b[i]]
			//greater one is selected, then perform u queries
			//printf("%d: %d %d\n", i, t, u);
			if(b[i]>a[i])++u;
			if(u&1)
				f+=v[b[i]];
			else
				f+=v[a[i]];
		}
	}
	printf("%lld\n", f);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:65:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i), v[V++]=a[i];
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:66:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b+i), v[V++]=b[i];
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:68:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<K;++i) scanf("%d", t+i), v[V++]=t[i];
                       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 21 ms 2944 KB Output is correct
15 Runtime error 31 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 21 ms 2944 KB Output is correct
15 Runtime error 31 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -