oj.uz

답안 #240272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240272 2020-06-19T06:04:27 Z frodakcin 운세 보기 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -