Submission #4352943


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll _v):v(normS(_v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ModInt& operator++(int){ return *this=*this+1;}
	ModInt& operator--(int){ return *this=*this-1;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll p[]={a,1,0},q[]={b,0,1};
		while(*q){
			ll t=*p/ *q;
			rep(i,3) swap(p[i]-=t*q[i],q[i]);
		}
		if(p[0]<0) rep(i,3) p[i]=-p[i];
		x=p[1],y=p[2];
		return p[0];
	}
	ModInt inv() const {
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	ModInt pow(ll p) const {
		ModInt a = 1;
		ModInt x = *this;
		while(p){
			if(p&1) a *= x;
			x *= x;
			p >>= 1;
		}
		return a;
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;

template<class D>
struct segtree{
	int N;
	vector<D> val;

	segtree(){}
	segtree(int n){
		N=1;
		while(N<n) N*=2;
		val.assign(N*2,D::e());
	}
	segtree(const vector<D>& ds){
		int n = ds.size();
		N=1;
		while(N<n) N*=2;
		val.assign(N*2,D::e());
		rep(i,n) val[i+N] = ds[i];
		for(int i=N-1;i>0;i--) val[i] = val[i*2] + val[i*2+1];
	}
	void assign(int k,D d){
		k+=N;
		val[k]=d;
		k/=2;
		while(k){
			val[k] = val[k*2] + val[k*2+1];
			k/=2;
		}
	}
	D query(int a,int b){		//non-commutative & unrecursive
		D L = D::e() , R = D::e();
		a+=N,b+=N;
		while(a<b){
			if(a&1) L = L + val[a++];
			if(b&1) R = val[--b] + R;
			a/=2,b/=2;
		}
		return L+R;
	}
};

VV<mint> e = {{1,0},{0,1}};
VV<mint> operator* (VV<mint> a,VV<mint> b){
	VV<mint> c(2,V<mint>(2,0));
	rep(i,2) rep(j,2) rep(k,2) c[i][j] += a[i][k]*b[k][j];
	return c;
}
VV<mint> ex(VV<mint> x, int p){
	VV<mint> a = e;
	while(p){
		if(p&1) a = a * x;
		x = x * x;
		p /= 2;
	}
	return a;
}

struct D{
	VV<mint> a;
	D(){*this = e();}
	D(VV<mint> _a):a(_a){}
	static D e(){
		return D(::e);
	}
	D operator+(const D& r) const {
		return D(a*r.a);
	}
};

struct Query{
	int t;
	int x;
	int l,r;
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!

	int N,Q;
	cin>>N>>Q;
	V<int> xs;
	V<Query> qs;
	rep(q,Q){
		int t;
		cin>>t;
		if(t==1){
			int x;
			cin>>x;
			x--;
			xs.pb(x);
			xs.pb(x+1);
			qs.pb({1,x,0,0});
		}else{
			int l,r;
			cin>>l>>r;
			l--,r--;
			xs.pb(l);
			xs.pb(r);
			qs.pb({2,0,l,r});
		}
	}
	xs.pb(N);
	sort(all(xs));
	xs.erase(unique(all(xs)),xs.end());
	N = xs.size();

	auto getID = [&](int x){
		return lower_bound(all(xs),x) - xs.begin();
	};


	VV<mint> f = {{1,1},{1,0}};
	VV<mint> b = {{0,0},{1,0}};

	V<D> vs;
	rep(i,N-1){
		int len = xs[i+1]-xs[i];
		vs.pb(D(ex(f,len)));
	}
	segtree<D> seg(vs);

	set<int> block;

	for(auto q: qs){
		if(q.t==1){
			int x = q.x;
			bool bl = block.count(x);
			int id = getID(x);
			seg.assign(id,bl ? f : b);
			if(bl) block.erase(x);
			else block.insert(x);
		}else{
			int l = q.l, r = q.r;
			if(block.count(l) || block.count(r)){
				cout<<0<<endl;
				continue;
			}
			int lid = getID(l);
			int rid = getID(r);
			auto A = seg.query(lid,rid).a;
			cout<<A[0][0]<<endl;
		}
	}
}

Submission Info

Submission Time
Task D - Dangerous Hopscotch
User sigma425
Language C++14 (GCC 5.4.1)
Score 900
Code Size 5056 Byte
Status
Exec Time 3095 ms
Memory 114656 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
× 2
× 32
Set Name Test Cases
Sample 01.txt, 02.txt
All 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 2 ms 256 KB
14.txt 2850 ms 114272 KB
15.txt 2875 ms 113120 KB
16.txt 2843 ms 112992 KB
17.txt 416 ms 3052 KB
18.txt 410 ms 3052 KB
19.txt 249 ms 3052 KB
20.txt 249 ms 3052 KB
21.txt 377 ms 3052 KB
22.txt 377 ms 3052 KB
23.txt 382 ms 3052 KB
24.txt 377 ms 3052 KB
25.txt 383 ms 3052 KB
26.txt 2483 ms 114656 KB
27.txt 2489 ms 114656 KB
28.txt 2456 ms 114656 KB
29.txt 2485 ms 114656 KB
30.txt 2482 ms 114656 KB
31.txt 3014 ms 111968 KB
32.txt 3095 ms 112608 KB
33.txt 2965 ms 111328 KB
34.txt 3010 ms 112352 KB
35.txt 2999 ms 111328 KB
36.txt 2742 ms 112992 KB
37.txt 2749 ms 112992 KB
38.txt 2772 ms 113760 KB
39.txt 2756 ms 112992 KB
40.txt 2741 ms 112992 KB