oj.uz

Submission #48782

# Submission time Handle Problem Language Result Execution time Memory
48782 2018-05-18T17:44:52 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 1544 ms 107616 KB 
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
map<int,int> m;
vector<int> zh,aq[MAXN];
int a[2][MAXN],t[MAXN],seg[4*MAXN],bit[4*MAXN],lf[MAXN];
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) {for(int i=ind;i<=MAXN;i+=(i&-i)) bit[i]++;}
int fval(int ind) 
{
	int sol=0;
	for(int i=ind;i;i-=(i&-i)) sol+=bit[i];
	return sol;
}
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());
	int sz=zh.size();
	for(int i=0;i<zh.size();i++) m[zh[i]]=i+1;
	for(int i=1;i<=k;i++) upd(1,sz,m[t[i]],i,1);
	for(int i=0;i<n;i++) lf[i]=nmax(1,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((fval(MAXN)-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((fval(MAXN)-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:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<zh.size();i++) m[zh[i]]=i+1;
              ~^~~~~~~~~~
fortune_telling2.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<aq[i].size();j++)
               ~^~~~~~~~~~~~~
fortune_telling2.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<aq[0].size();j++)
              ~^~~~~~~~~~~~~
fortune_telling2.cpp:34: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:35: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:36: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 14 ms 12152 KB Output is correct
2 Correct 12 ms 12260 KB Output is correct
3 Correct 12 ms 12428 KB Output is correct
4 Correct 13 ms 12440 KB Output is correct
5 Correct 14 ms 12496 KB Output is correct
6 Correct 14 ms 12548 KB Output is correct
7 Correct 14 ms 12572 KB Output is correct
8 Correct 12 ms 12572 KB Output is correct
9 Correct 14 ms 12576 KB Output is correct
10 Correct 14 ms 12576 KB Output is correct
11 Correct 16 ms 12576 KB Output is correct
12 Correct 17 ms 12576 KB Output is correct
13 Correct 15 ms 12576 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 14444 KB Output is correct
2 Correct 120 ms 16608 KB Output is correct
3 Correct 208 ms 18920 KB Output is correct
4 Correct 279 ms 20964 KB Output is correct
5 Correct 286 ms 20964 KB Output is correct
6 Correct 273 ms 20964 KB Output is correct
7 Correct 301 ms 20964 KB Output is correct
8 Correct 381 ms 21160 KB Output is correct
9 Correct 177 ms 21160 KB Output is correct
10 Correct 167 ms 21160 KB Output is correct
11 Correct 145 ms 21160 KB Output is correct
12 Correct 155 ms 21160 KB Output is correct
13 Correct 172 ms 21160 KB Output is correct
14 Correct 173 ms 21160 KB Output is correct
15 Correct 189 ms 21160 KB Output is correct
16 Correct 246 ms 21160 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 27480 KB Output is correct
2 Correct 1028 ms 34680 KB Output is correct
3 Correct 1394 ms 41120 KB Output is correct
4 Runtime error 1544 ms 107616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -