Submission #670924

#	Time	Username	Problem	Language	Result	Execution time	Memory
670924		nolimiya	Plus Minus (BOI17_plusminus)	C++14	100 / 100	112 ms	19864 KiB

plusminus

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<int , bool>
#define pii pair<long long , pair<long long , long long>>
const int maxm =5e5 + 5;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<pi> g , z;
ll sath[maxm];
bool vis[maxm] , gos[maxm];
ll pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
void merge(ll r , ll q){
    if (get_par(r)!=get_par(q))l+=max(darage[r],darage[q])*1ll*sath[r]*1ll*sath[q];
    r = get_par(r) , q = get_par(q);
    if (r!=q){
        if (sath[r]<sath[q]) swap(r,q);
        pedaret[q] = r;
        sath[r] += sath[q];
    }
    return ;
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
int rp[maxm];
pi w[maxm];
multiset<ll> st,ts;
//ll rw[maxm][maxm];
map<ll,ll> mp;
ll pw(ll x , ll y){
	if (y==0) return 1;
	if (y%2==0) return ((pw(x,y/2)%mod)*pw(x,y/2)%mod)%mod;
	return x*(((pw(x,y/2)%mod)*pw(x,y/2)%mod)%mod)%mod;
}
ll dvide(vector<pi>&g,vector<pi>&z,ll n,ll m,ll ss){ 
	mp.clear();
	for(int i=0; i<ss; i++){ 
		ll x=g[i].first,y=z[i].first;
		vis[2]=g[i].second,vis[3] = 0; 
		if(x%2==0) vis[3]=vis[2]; 
		else vis[3]=(1-vis[2]);
		if(!mp.count(y)) mp[y]=vis[3];
		else if(mp[y]!=vis[3]) return 0;
	}
	return pw(2,m-mp.size());
}
int main(){
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >>n>>m>>ss;
    vis[0] = vis[1] = 1;
    for (int i=0; i<ss; i++){
    	char x;
    	cin >>x>>l>>r,l--,r--;
    	vis[0]&=(!(!(l&1)^!(r&1))==(x=='+'));
		vis[1]&=(!(!(l&1)^!(r&1))==(x!='+'));		
		g.push_back({l,(x=='+')});
		z.push_back({r,(x=='+')});	
    }
    cout<<ll(dvide(g,z,n,m,ss)+dvide(z,g,m,n,ss)-vis[0]-vis[1])%mod;
}

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46