oj.uz

답안 #205682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205682 2020-02-29T13:25:28 Z GioChkhaidze 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 5 ms 504 KB 
#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int Nm=2e5+5;
ll ans;
int n,q,L,R,S;
int l[Nm],r[Nm],t[Nm];
int G[3*Nm],Last[3*Nm],Rf[3*Nm],v[6*Nm];
pair < int , int > Id[Nm];
vector < int > s;
map < int , int > f;

void Build(Tree) {
	if (l==r) { v[h]=Last[l]; return ;}
	Build(Left),Build(Right);
	v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}

int Get(Tree) {
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return v[h];
	int x=Get(Left),y=Get(Right);
	return max(x,y);
}

void Up(int x) {
	while (x<=S) {
		G[x]++;
		x+=(x & -x);
	}
}

int Ge(int x) {
	int res=0;
	while (x>0) {
		res+=G[x];
		x-=(x & -x);
	}
	return res;
}


main () {
	scanf("%d%d",&n,&q);
	for (int i=1; i<=n; i++) {
		scanf("%d%d",&l[i],&r[i]);
		s.pb(l[i]),s.pb(r[i]);
	}
	
	for (int i=1; i<=q; i++) {
		scanf("%d",&t[i]);
		s.pb(t[i]);
	}
	
	sort(s.begin(),s.end());
	s.erase(unique(s.begin(),s.end()),s.end());
	
	for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
	for (int i=1; i<=n; i++) l[i]=f[l[i]],r[i]=f[r[i]];
	for (int i=1; i<=q; i++) t[i]=f[t[i]];
	
	S=s.size();
	
	for (int i=1; i<=q; i++) Last[t[i]]=i;
	Build(1,1,S);
	
	for (int i=1; i<=n; i++) {
		L=min(l[i],r[i]),R=max(l[i],r[i])-1;
		Id[i].F=Get(1,1,S),Id[i].S=i;
	}
	
	sort(Id+1,Id+n+1);
	
	int Q=q,tot=0;
	for (int i=n; i>=1; i--) {
		while (Q && Id[i].F<Q) Up(t[Q]),--Q;
		tot=Ge(S)-Ge(max(l[Id[i].S],r[Id[i].S])-1);
		
		if (Id[i].F && l[Id[i].S]<r[Id[i].S]) 
			swap(l[Id[i].S],r[Id[i].S]);

		if (tot%2) 
			ans+=Rf[r[Id[i].S]];
				else 
			ans+=Rf[l[Id[i].S]];
	}	
	
	printf("%I64d\n",ans);
}

Compilation message

fortune_telling2.cpp:49:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
                ~^~~~~~~~~
fortune_telling2.cpp:94:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%I64d\n",ans);
                      ^
fortune_telling2.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -