Submission #20664

#	Time	Username	Problem	Language	Result	Execution time	Memory
20664		우리OJ (#35)	초음속철도 (OJUZ11_rail)	C++14	100 / 100	579 ms	21532 KiB

rail

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;

int n, m;
int xs[400040], xz;
Pi p[200020];

const int MOD = 1e9 + 7;

struct node{
	node(){sum = 0, C = 1;}
	ll sum, C;
}T[1<<20];

void add(int rt, int l, int r, int x, ll v){
	if(l == r){
		T[rt].sum = (T[rt].sum + v) % MOD;
		return;
	}
	if(T[rt].C != 1){
		T[rt<<1].C = (T[rt<<1].C * T[rt].C) % MOD;
		T[rt<<1|1].C = (T[rt<<1|1].C * T[rt].C) % MOD;
		T[rt<<1].sum = (T[rt<<1].sum * T[rt].C) % MOD;
		T[rt<<1|1].sum = (T[rt<<1|1].sum * T[rt].C) % MOD;
		T[rt].C = 1;
	}
	int m = (l + r) >> 1;
	if(x <= m)add(rt<<1, l, m, x, v);
	else add(rt<<1|1, m+1, r, x, v);
	T[rt].sum = (T[rt<<1].sum + T[rt<<1|1].sum) % MOD;
}

ll get_sum(int rt, int l,int r, int s, int d){
	if(s <= l && r <= d){
		return T[rt].sum;
	}
	if(T[rt].C != 1){
		T[rt<<1].C = (T[rt<<1].C * T[rt].C) % MOD;
		T[rt<<1|1].C = (T[rt<<1|1].C * T[rt].C) % MOD;
		T[rt<<1].sum = (T[rt<<1].sum * T[rt].C) % MOD;
		T[rt<<1|1].sum = (T[rt<<1|1].sum * T[rt].C) % MOD;
		T[rt].C = 1;
	}
	int m = (l + r) >> 1;
	ll res = 0;
	if(s <= m)res += get_sum(rt<<1, l, m, s, d);
	if(m < d)res += get_sum(rt<<1|1, m+1, r, s, d);
	return res % MOD;
}

void mul2(int rt, int l, int r, int s, int d){
	if(s <= l && r <= d){
		T[rt].sum = (T[rt].sum + T[rt].sum) % MOD;
		T[rt].C = (T[rt].C + T[rt].C) % MOD;
		return;
	}
	if(T[rt].C != 1){
		T[rt<<1].C = (T[rt<<1].C * T[rt].C) % MOD;
		T[rt<<1|1].C = (T[rt<<1|1].C * T[rt].C) % MOD;
		T[rt<<1].sum = (T[rt<<1].sum * T[rt].C) % MOD;
		T[rt<<1|1].sum = (T[rt<<1|1].sum * T[rt].C) % MOD;
		T[rt].C = 1;
	}
	int m = (l + r) >> 1;
	if(s <= m)mul2(rt<<1, l, m, s, d);
	if(m < d)mul2(rt<<1|1, m+1, r, s, d);
	T[rt].sum = (T[rt<<1].sum + T[rt<<1|1].sum) % MOD;
}

void solve(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=m;i++){
		int s, e;
		scanf("%d%d", &s, &e);
		p[i] = Pi(s, e);
		xs[xz++] = s, xs[xz++] = e;
	}
	xs[xz++] = 1; xs[xz++] = n;
	sort(xs, xs + xz);
	xz = (int)(unique(xs, xs + xz) - xs);
	for(int i=1;i<=m;i++){
		p[i].Fi = (int)(lower_bound(xs, xs + xz, p[i].Fi) - xs) + 1;
		p[i].Se = (int)(lower_bound(xs, xs + xz, p[i].Se) - xs) + 1;
	}
	add(1, 1, xz, 1, 1);
	sort(p+1, p+1+m);
	for(int i=1;i<=m;i++){
		int l = p[i].Fi, r = p[i].Se;
		if(l != 1)mul2(1, 1, xz, 1, l-1);
		if(r != xz)mul2(1, 1, xz, r+1, xz);
		ll s = get_sum(1, 1, xz, l, r);
		add(1, 1, xz, r, s);
	}
	printf("%lld\n", get_sum(1, 1, xz, xz, xz));
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Compilation message (stderr)

rail.cpp: In function 'void solve()':
rail.cpp:100:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
rail.cpp:103:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
                        ^

• Subtask 1: 10 / 10
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 27 / 27
• Subtask 5: 30 / 30