oj.uz

Submission #48776

# Submission time Handle Problem Language Result Execution time Memory
48776 2018-05-18T17:34:27 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 714 ms 60440 KB 
#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
map<int,int> m;
vector<int> zh,aq[2*MAXN];
int a[2][MAXN],t[MAXN],seg[4*MAXN],bit[4*MAXN],inv[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<=zh.size();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;
	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(sz)-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(sz)-fval(m[c]))%2==0) sol+=b;
		else sol+=c;
	}
	printf("%lld",sol);
}

Compilation message

fortune_telling2.cpp: In function 'void updf(int)':
fortune_telling2.cpp:23:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 void updf(int ind) {for(int i=ind;i<=zh.size();i+=(i&-i)) bit[i]++;}
                                   ~^~~~~~~~~~~
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;
              ~^~~~~~~~~~
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 11 ms 9848 KB Output is correct
2 Correct 13 ms 10088 KB Output is correct
3 Correct 12 ms 10088 KB Output is correct
4 Correct 12 ms 10088 KB Output is correct
5 Correct 24 ms 10088 KB Output is correct
6 Correct 14 ms 10088 KB Output is correct
7 Correct 12 ms 10112 KB Output is correct
8 Correct 14 ms 10112 KB Output is correct
9 Correct 10 ms 10164 KB Output is correct
10 Correct 10 ms 10164 KB Output is correct
11 Correct 10 ms 10164 KB Output is correct
12 Correct 13 ms 10164 KB Output is correct
13 Correct 14 ms 10188 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 12108 KB Output is correct
2 Correct 122 ms 14236 KB Output is correct
3 Correct 261 ms 16708 KB Output is correct
4 Correct 310 ms 18416 KB Output is correct
5 Correct 295 ms 18416 KB Output is correct
6 Correct 300 ms 18500 KB Output is correct
7 Correct 276 ms 18604 KB Output is correct
8 Correct 206 ms 18724 KB Output is correct
9 Correct 165 ms 18724 KB Output is correct
10 Correct 152 ms 18724 KB Output is correct
11 Correct 150 ms 18724 KB Output is correct
12 Correct 168 ms 18724 KB Output is correct
13 Correct 178 ms 18724 KB Output is correct
14 Correct 203 ms 18724 KB Output is correct
15 Correct 188 ms 18724 KB Output is correct
16 Correct 240 ms 18724 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 25020 KB Output is correct
2 Runtime error 707 ms 60440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -