oj.uz

Submission #48792

# Submission time Handle Problem Language Result Execution time Memory
48792 2018-05-18T18:13:54 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 784 ms 71516 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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