IOITC 2014 Marathon

marathon.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
using namespace std;

const int maxn = int(2e5)+5, inf = int(1e9)+5, MOD = int(1e9)+7;

int nex[maxn], dp[maxn], BIT[maxn];
pair<int, int> A[maxn];
vector<pair<int, int>> events[maxn];

inline int INTMOD(int a, int b) { return ((a%b)+b)%b; }

void upd(int idx, int v)
{
	while(idx < maxn)
	{
		BIT[idx] += v;
		BIT[idx] %= MOD;
		idx += (idx&-idx);
	}
}

int qry(int idx)
{
	int res = 0;
	while(idx)
	{
		res += BIT[idx]%MOD;
		res %= MOD;
		idx -= (idx&-idx);
	}
	return res;
}

int main(void)
{
	int n;
	scanf("%d", &n);
	vector<int> mapper;
	for(int i = 1;i <= n;i++)
	{
		scanf("%d%d", &A[i].first, &A[i].second);
		mapper.push_back(A[i].first), mapper.push_back(A[i].second);
	}

	sort(mapper.begin(), mapper.end());
	mapper.resize(int(unique(mapper.begin(), mapper.end())-mapper.begin()));

	int idx = 1;
	map<int, int> mp;
	for(auto it: mapper) mp[it] = idx++;

	for(int i = 1;i <= n;i++)
	{
		A[i] = {mp[A[i].first], mp[A[i].second]};
	}

	sort(A+1, A+n+1);

	for(int i = 1;i <= n;i++) events[A[i].first].push_back({i, 0}), events[A[i].second].push_back({i, 1});

	A[n+1] = {inf, inf};
	int earlyend = n+1;
	for(int i = idx-1;i > 0;i--)
	{
		for(auto it: events[i])
		{
			if(it.second) nex[it.first] = earlyend;
		}
		for(auto it: events[i])
		{
			if(!it.second && A[earlyend].second >= A[it.first].second) earlyend = it.first;
		}
	}

	int miniend = inf;
	for(int i = n;i > 0;i--)
	{
		if(nex[i] == n+1) dp[i] = 1;
		else dp[i] = INTMOD(qry(A[nex[i]].second)%MOD-qry(A[i].second)%MOD, MOD);
		dp[i] %= MOD;
		upd(A[i].first, dp[i]);
		miniend = min(miniend, A[i].second);
	}

	int res = 0;
	for(int i = 1;i <= n;i++)
	{
		res += (A[i].first <= miniend)*dp[i]%MOD;
		res %= MOD;
	}
	
	printf("%d\n", res);
}

runner.sh

#!/bin/bash

for i in `seq 1 1000`; do
	echo $i
	./tester > inp$i.in
	./marathon_2 < inp$i.in > mera.out
	./MRJ < inp$i.in > ac.out
	diff -b mera.out ac.out
done

tester.cpp

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(1e5), maxv = int(1e9);

int main(void)
{
	srand(time(NULL));
	int n;
	n = rand()%maxn+1;
	printf("%d\n", n);
	for(int i = 0;i < n;i++)
	{
		int L = rand()%maxv+1, R = rand()%maxv+1;
		if(L > R) swap(L, R);
		printf("%d %d\n", L, R);
	}
}