Submission #20832

#	Time	Username	Problem	Language	Result	Execution time	Memory
20832		Namnamseo	초음속철도 (OJUZ11_rail)	C++14	100 / 100	773 ms	44224 KiB

rail

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back

pp data[200010];
int n;
vector<int> xp;

void in(){
	int p;
	read(p); xp.pb(1); xp.pb(p);
	read(n);
	for(int i=1; i<=n; ++i){
		int a, b; read(a, b);
		xp.pb(a); xp.pb(b); data[i]=pp{a, b};
	}
}

int xn;

void cc(){
	sort(all(xp));
	xp.erase(unique(all(xp)), xp.end());
	for(int i=1; i<=n; ++i){
		int a, b; tie(a, b) = data[i];
		a = lower_bound(all(xp), a) - xp.begin();
		b = lower_bound(all(xp), b) - xp.begin();
		data[i] = pp{a, b};
	}
	xn = xp.size();
}

const ll M=1'000'000'007;
const ll inv2=(M+1)/2;
ll dp[200010];
ll p2[400010];

auto rcmp = [](const pp& a, const pp& b){ return a.second < b.second; };

struct SEG {
	static const int T=524288;
	ll tsum[T<<1];
	ll tdp [T<<1];
	ll ttwo[T<<1];
	ll lazy[T<<1];
	void init(){
		for(auto& x:ttwo) x=1;
		for(auto& x:lazy) x=1;
	}
	void pd(int l, int r, int p){
		if(l==r || lazy[p]==1) return;
		for(int i=0; i<2; ++i){
			int x=p*2+i;
			tsum[x] = (tsum[x]*lazy[p])%M;
			ttwo[x] = (ttwo[x]*lazy[p])%M;
			lazy[x] = (lazy[x]*lazy[p])%M;
		}
		lazy[p]=1;
	}
	void divhalf(int l, int r, int ml=0, int mr=n, int p=1){
		pd(ml, mr, p);
		if(r<ml || mr<l) return;
		if(l<=ml && mr<=r){
			tsum[p] = (tsum[p]*inv2)%M;
			ttwo[p] = (ttwo[p]*inv2)%M;
			lazy[p] = inv2;
			return;
		}
		int mid=(ml+mr)/2;
		divhalf(l, r, ml, mid, p*2);
		divhalf(l, r, mid+1, mr, p*2+1);
		tsum[p]=(tsum[p*2]+tsum[p*2+1])%M;
	}
	ll rsum(int l, int r, int ml=0, int mr=n, int p=1){
		pd(ml, mr, p);
		if(r<ml || mr<l) return 0;
		if(l<=ml && mr<=r) return tsum[p];
		int mid=(ml+mr)/2;
		return rsum(l, r, ml, mid, p*2) + rsum(l, r, mid+1, mr, p*2+1);
	}
	void upd(int up, ll uv, int ml=0, int mr=n, int p=1){
		pd(ml, mr, p);
		if(up<ml || mr<up) return;
		if(ml==up && mr==up){
			tdp[p]=uv;
			tsum[p]=(tdp[p]*ttwo[p])%M;
			return;
		}
		int mid=(ml+mr)/2;
		upd(up, uv, ml, mid, p*2);
		upd(up, uv, mid+1, mr, p*2+1);
		tsum[p]=(tsum[p*2]+tsum[p*2+1])%M;
	}
} seg;

int main()
{
	//freopen("in", "r", stdin);
    in(); cc();
    
    p2[0]=1; for(int i=1; i<=400000; ++i) p2[i]=(p2[i-1]*2)%M;
    
    sort(data+1, data+n+1, rcmp);
    
    seg.init();
    dp[0]=1; seg.upd(0, 1);
    
    for(int i=1; i<=n; ++i){
		int a, b; tie(a, b) = data[i];
		int last = lower_bound(data, data+n+1, pp{0, a}, rcmp)-data-1;
		ll invdp = seg.rsum(0, last);
		invdp = (invdp * p2[i-1])%M;
		dp[i] = (p2[i-1]-invdp+M)%M;
		seg.divhalf(last+1, n);
		seg.upd(i, dp[i]);
    }
    
    ll ans=0;
    for(int i=1; i<=n; ++i) if(data[i].second == xn-1) ans = (ans+dp[i])%M;
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

rail.cpp: In function 'void read(int&)':
rail.cpp:5:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^

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