[ create a new paste ] login | about

Link: http://codepad.org/lwdVNWrc    [ raw code | output | fork ]

C++, pasted on Apr 1:
#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define re(i, n) for (int i=0; i<n; i++)

#define re1(i, n) for (int i=1; i<=n; i++)

#define re2(i, l, r) for (int i=l; i<r; i++)

#define re3(i, l, r) for (int i=l; i<=r; i++)

#define rre(i, n) for (int i=n-1; i>=0; i--)

#define rre1(i, n) for (int i=n; i>0; i--)

#define rre2(i, r, l) for (int i=r-1; i>=l; i--)

#define rre3(i, r, l) for (int i=r; i>=l; i--)

#define ll long long

#define LCH(i) (i << 1)

#define RCH(i) ((i << 1) + 1)

#define root 1

const int MAXN = 300010, MAXM = 600100, INF = ~0U >> 2;

struct node {

	int sum;

	bool FF;

} T[MAXM << 2];

int n, m, X[MAXN], Y[MAXN], A[MAXM], l0, r0;

ll res;

void init()

{

	int s; scanf("%d%d", &n, &s); A[1] = 0; A[2] = s; m = 2;

	re(i, n) {

		scanf("%d%d", &X[i], &Y[i]);

		A[m++] = X[i]; A[m++] = Y[i];

	}

	res = s;

}

int find_x(int x)

{

	int l = 0, r = m - 1, mid;

	while (1) {

		mid = l + r >> 1;

		if (x == A[mid]) return mid; else if (x < A[mid]) r = mid - 1; else l = mid + 1;

	}

}

void prepare()

{

	sort(A, A + m);

	int m0 = 1; re2(i, 1, m) if (A[i] > A[i - 1]) A[m0++] = A[i]; m = m0;

	re(i, n) {X[i] = find_x(X[i]); Y[i] = find_x(Y[i]);}

}

void opr(int l, int r, int No)

{

	if (l >= l0 && r <= r0) {T[No].FF = 1; T[No].sum = A[r + 1] - A[l];} else {

		int mid = l + r >> 1;

		if (mid >= l0) opr(l, mid, LCH(No));

		if (mid < r0) opr(mid + 1, r, RCH(No));

		if (!T[No].FF) T[No].sum = T[LCH(No)].sum + T[RCH(No)].sum;

	}

}

void solve()

{

	re(i, n) if (X[i] > Y[i]) {l0 = Y[i]; r0 = X[i] - 1; opr(0, m - 1, root);}

	res += T[root].sum << 1;

}

void pri()

{

	cout << res << endl;

}

int main()

{

	init();

	prepare();

	solve();

	pri();

	return 0;

}


Output:
1
2
Line 49: error: ISO C++ does not support 'long long'
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: