Submission #20418

#	Time	Username	Problem	Language	Result	Execution time	Memory
20418		tlwpdus (#35)	초음속철도 (OJUZ11_rail)	C++98	100 / 100	666 ms	43976 KiB

rail

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;

const ll MOD = 1000000007;
ll po[200100] = {1};

struct node {
	ll val, rex;
	node *l, *r;
	node(){val=rex=0;l=r=0;}
	void pd() {
		l->val *= po[rex];
		l->val %= MOD;
		r->val *= po[rex];
		r->val %= MOD;
		l->rex += rex;
		r->rex += rex;
		rex = 0;
	}
	void pu() {
		val = (l->val + r->val)%MOD;
	}
	void init(int s, int e) {
		if (s==e) {
			return;
		}
		int m = (s+e)>>1;
		l = new node();
		l -> init(s,m);
		r = new node();
		r -> init(m+1,e);
	}
	void upd(int s, int e, int idx, ll v) {
		if (e<idx||idx<s) return;
		if (s==e) {
			val += v;
			val %= MOD;
			return;
		}
		int m = (s+e)>>1;
		pd();
		l -> upd(s,m,idx,v);
		r -> upd(m+1,e,idx,v);
		pu();
	}
	void upde(int s, int e, int S, int E, ll ex) {
		if (e<S||E<s) return;
		if (S<=s&&e<=E) {
			rex += ex;
			val *= po[ex];
			val %= MOD;
			return;
		}
		int m = (s+e)>>1;
		pd();
		l -> upde(s,m,S,E,ex);
		r -> upde(m+1,e,S,E,ex);
		pu();
	}
	ll getv(int s, int e, int S, int E) {
		if (e<S||E<s) return 0;
		if (S<=s&&e<=E) {
			return val;
		}
		int m = (s+e)>>1;
		pd();
		ll res = (l -> getv(s,m,S,E) + r -> getv(m+1,e,S,E))%MOD;
		pu();
		return res;
	}
} *head;

int n, m;

vector<int> comp;
pii arr[200100];

bool cmpi(pii a, pii b) {
	return a.second<b.second||(a.second==b.second&&a.first<b.first);
}
int main() {
	int i;
	scanf("%d%d",&n,&m);
	comp.push_back(1);
	comp.push_back(n);
	for (i=1;i<=m+10;i++) po[i] = (po[i-1]*2)%MOD;
	for (i=0;i<m;i++) {
		scanf("%d%d",&arr[i].first,&arr[i].second);
		comp.push_back(arr[i].first);
		comp.push_back(arr[i].second);
	}
	sort(comp.begin(),comp.end());
	comp.erase(unique(comp.begin(),comp.end()),comp.end());
	n = (int)comp.size()-1;
	for (i=0;i<m;i++) {
		arr[i].first = lower_bound(comp.begin(),comp.end(),arr[i].first)-comp.begin();
		arr[i].second = lower_bound(comp.begin(),comp.end(),arr[i].second)-comp.begin();
	}
	sort(arr,arr+m,cmpi);
	head = new node();
	head->init(0,n);
	head->upd(0,n,0,1);
	for (i=0;i<m;i++) {
		head->upd(0,n,arr[i].second,head->getv(0,n,arr[i].first,arr[i].second));
		if (arr[i].first>0) head->upde(0,n,0,arr[i].first-1,1);
	}
	printf("%lld\n",head->getv(0,n,n,n));

	return 0;
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:91:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
rail.cpp:96:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&arr[i].first,&arr[i].second);
                                             ^

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