Submission #295392

#	Time	Username	Problem	Language	Result	Execution time	Memory
295392		patrikpavic2	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	779 ms	124256 KiB

fortune_telling2

#include <cstdio>
#include <vector>
#include <algorithm>

#define PB push_back

using namespace std;

typedef long long ll;
typedef vector < int > vi;

const int N = 4e5 + 500;
const int OFF = (1 << 19);

int n, q, A[N], B[N], Q[N];
int loga[N], l_siz, izb[N];
vi saz, T[2 * OFF];

void add(int x){
	l_siz++;
	for(x += 5 ; x < N ; x += x & -x)
		loga[x]++;
}

int query(int x){
	x--;
	int ret = 0;
	for(x += 5 ; x ; x -= x & -x)
		ret += loga[x];
	return l_siz - ret;
}

ll sol = 0;

void izbaci(int i){
	if(izb[i]) return;
	izb[i] = 1;
	if(query(B[i]) & 1)
		sol += saz[min(A[i], B[i])];
	else
		sol += saz[max(A[i], B[i])];
}

void dodaj(int i, int a, int b, int lo, int hi, int x){
	if(lo <= a && b <= hi){
		T[i].PB(x); return;
	}	
	if(a > hi || b < lo) return;
	dodaj(2 * i, a, (a + b) / 2, lo, hi, x);
	dodaj(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}

void unisti(int x){
	x += OFF;
	for(; x ; x /= 2){
		for(int y : T[x])
			izbaci(y);
		T[x].clear();
	}
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++){
		scanf("%d%d", A + i, B + i);
		saz.PB(A[i]), saz.PB(B[i]);
	}
	for(int i = 0;i < q;i++){
		scanf("%d", Q + i);
		saz.PB(Q[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 0;i < n;i++){
		A[i] = lower_bound(saz.begin(), saz.end(), A[i]) - saz.begin();
		B[i] = lower_bound(saz.begin(), saz.end(), B[i]) - saz.begin();
	}
	for(int i = 0;i < q;i++){
		Q[i] = lower_bound(saz.begin(), saz.end(), Q[i]) - saz.begin();
	}
	for(int i = 0;i < n;i++){
		if(A[i] == B[i]){
			izb[i] = 1;
			sol += saz[A[i]]; continue;
		}
		dodaj(1, 0, OFF - 1, min(A[i], B[i]), max(A[i], B[i]) - 1, i);
	}
	for(int i = q - 1;i >= 0;i--){
		unisti(Q[i]); add(Q[i]);
	}
	for(int i = 0;i < n;i++){
		if(!izb[i]){
			if(query(B[i]) & 1)
				sol += saz[B[i]];
			else
				sol += saz[A[i]];
		}
	}
	printf("%lld\n", sol);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d%d", A + i, B + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", Q + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65