답안 #48792 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48792	2018-05-18T18:13:54 Z	Pajaraja	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	784 ms	71516 KB

fortune_telling2

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
vector<int> zh,aq[MAXN];
int a[2][MAXN],t[MAXN],seg[12*MAXN],bit[3*MAXN+7],lf[MAXN],uk,sz;
void upd(int l,int r,int v,int val,int ind)
{
	if(l==r) {seg[ind]=val; return;}
	int s=(l+r)/2;
	if(s>=v) upd(l,s,v,val,2*ind);
	else upd(s+1,r,v,val,2*ind+1);
	seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}
int nmax(int l,int r,int lt,int rt,int ind)
{
	if(l>r) return 0;
	if(l>=lt  && r<=rt) return seg[ind];
	if(r<lt || l>rt) return 0;
	int s=(l+r)/2;
	return max(nmax(l,s,lt,rt,2*ind),nmax(s+1,r,lt,rt,2*ind+1));
}
void updf(int ind) {uk++; for(int i=ind;i<=3*MAXN;i+=(i&-i)) bit[i]++;}
int fval(int ind) 
{
	int sol=0;
	for(int i=ind;i>0;i-=(i&-i)) sol+=bit[i];
	return sol;
}
int binarna(int l,int r,int val)
{
	if(l==r) return l;
	int s=(l+r)/2;
	if(val<zh[s]) return binarna(l,s,val);
	return binarna(s+1,r,val);
}
int m(int x){return binarna(0,sz-1,x);}
int main()
{
	int n,k;
	long long sol=0;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) {scanf("%d%d",&a[0][i],&a[1][i]); zh.push_back(a[0][i]); zh.push_back(a[1][i]);}
	for(int i=1;i<=k;i++) {scanf("%d",&t[i]); zh.push_back(t[i]);}
	sort(zh.begin(),zh.end());
	sz=zh.size();
	for(int i=1;i<=k;i++) upd(0,sz,m(t[i]),i,1);
	for(int i=0;i<n;i++) lf[i]=nmax(0,sz,m(min(a[0][i],a[1][i])),m(max(a[0][i],a[1][i]))-1,1);
	for(int i=0;i<n;i++) aq[lf[i]].push_back(i);
	for(int i=k;i>=1;i--)
	{
		updf(m(t[i])+1);
		for(int j=0;j<aq[i].size();j++)
		{
			int b=min(a[0][aq[i][j]],a[1][aq[i][j]]),c=max(a[0][aq[i][j]],a[1][aq[i][j]]);
			if((uk-fval(m(c)))%2==0) sol+=c;
			else sol+=b; 
		}
	}
	for(int j=0;j<aq[0].size();j++)
	{
		int b=a[0][aq[0][j]],c=a[1][aq[0][j]];
		if((uk-fval(m(c)))%2==0) sol+=b;
		else sol+=c;
	}
	printf("%lld",sol);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<aq[i].size();j++)
               ~^~~~~~~~~~~~~
fortune_telling2.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<aq[0].size();j++)
              ~^~~~~~~~~~~~~
fortune_telling2.cpp:41: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:42:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) {scanf("%d%d",&a[0][i],&a[1][i]); zh.push_back(a[0][i]); zh.push_back(a[1][i]);}
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:43:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=k;i++) {scanf("%d",&t[i]); zh.push_back(t[i]);}
                         ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	7 ms	5228 KB	Output is correct
3	Correct	9 ms	5280 KB	Output is correct
4	Correct	8 ms	5328 KB	Output is correct
5	Correct	9 ms	5384 KB	Output is correct
6	Correct	12 ms	5404 KB	Output is correct
7	Correct	9 ms	5404 KB	Output is correct
8	Correct	8 ms	5404 KB	Output is correct
9	Correct	7 ms	5404 KB	Output is correct
10	Correct	7 ms	5404 KB	Output is correct
11	Correct	8 ms	5404 KB	Output is correct
12	Correct	7 ms	5404 KB	Output is correct
13	Correct	8 ms	5404 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	6048 KB	Output is correct
2	Correct	52 ms	6716 KB	Output is correct
3	Correct	80 ms	7592 KB	Output is correct
4	Correct	111 ms	8092 KB	Output is correct
5	Correct	114 ms	8100 KB	Output is correct
6	Correct	109 ms	8168 KB	Output is correct
7	Correct	100 ms	8168 KB	Output is correct
8	Correct	104 ms	8296 KB	Output is correct
9	Correct	85 ms	8296 KB	Output is correct
10	Correct	83 ms	8296 KB	Output is correct
11	Correct	81 ms	8296 KB	Output is correct
12	Correct	84 ms	8400 KB	Output is correct
13	Correct	83 ms	8400 KB	Output is correct
14	Correct	98 ms	8400 KB	Output is correct
15	Correct	95 ms	8400 KB	Output is correct
16	Correct	108 ms	8400 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	230 ms	10156 KB	Output is correct
2	Correct	321 ms	13452 KB	Output is correct
3	Correct	466 ms	15152 KB	Output is correct
4	Correct	784 ms	22844 KB	Output is correct
5	Correct	216 ms	22844 KB	Output is correct
6	Correct	783 ms	22844 KB	Output is correct
7	Correct	734 ms	22844 KB	Output is correct
8	Correct	719 ms	22844 KB	Output is correct
9	Correct	697 ms	22844 KB	Output is correct
10	Correct	680 ms	22844 KB	Output is correct
11	Correct	652 ms	28880 KB	Output is correct
12	Correct	693 ms	34004 KB	Output is correct
13	Correct	578 ms	39724 KB	Output is correct
14	Correct	421 ms	40840 KB	Output is correct
15	Correct	419 ms	46600 KB	Output is correct
16	Correct	411 ms	52832 KB	Output is correct
17	Correct	417 ms	59180 KB	Output is correct
18	Correct	466 ms	63000 KB	Output is correct
19	Correct	473 ms	65652 KB	Output is correct
20	Correct	523 ms	71516 KB	Output is correct

답안 #48792

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0