oj.uz

Submission #154537

# Submission time Handle Problem Language Result Execution time Memory
154537 2019-09-22T14:58:26 Z phillip Usmjeri (COCI17_usmjeri) C++14
28 / 140
 853 ms 8720 KB 
#include <bits/stdc++.h>
#define lp (pos+pos+1)
#define rp (2*pos+2)
#define m (l+r)/2
using namespace std;
int pt;
int rep[500009],sz[500009],mod=1e9+7;
int find(int x)
{
    if(x==-1)return -1;
    while(x!=rep[x])x=rep[x];
    return x;
}
void cn(int x,int y)
{
    if(min(x,y)==-1)return;
    x=find(x);y=find(y);
    if(x==y)return;
    if(sz[x]<sz[y])swap(x,y);
    sz[x]+=sz[y];
    rep[y]=x;
}
int seg[1200009],a[300009];
void laz(int pos,int l,int r)
{
    if(seg[pos]==-1)return;
    seg[pos]=find(seg[pos]);
    if(l==r)
    {
        cn(seg[pos],a[l]);
        a[l]=find(seg[pos]);
        seg[pos]=-1;
        return;
    }
    cn(seg[pos],seg[lp]);
    cn(seg[pos],seg[rp]);
    seg[pos]=find(seg[pos]);
    seg[lp]=seg[pos];
    seg[rp]=seg[pos];
    seg[pos]=-1;
}
void upd(int pos,int l,int r,int b,int e,int o)
{
    laz(pos,l,r);
    if(b<=l&&r<=e)
    {
        seg[pos]=o;
        laz(pos,l,r);
        return;
    }
    if(m>=b)upd(lp,l,m,b,e,o);
    if(m<e)upd(rp,m+1,r,b,e,o);
}
void frsh(int pos,int l,int r)
{
    laz(pos,l,r);
    if(l==r)return;
    frsh(lp,l,m);
    frsh(rp,m+1,r);
}
int n,q,x,y;
int vis[300009];
int main()
{
    memset(a,-1,sizeof(a));
    memset(seg,-1,sizeof(seg));
    cin>>n>>q;
    for(int i=0;i<q;i++)
    {
        sz[i]=1;
        rep[i]=i;
    }
    for(int i=0;i<n-1;i++)cin>>x>>x;
    for(int i=0;i<q;i++)
    {
        cin>>x>>y;
        x--;y-=2;
        upd(0,0,n-2,x,y,i);
    }
    frsh(0,0,n-2);
    int ans=1;
    for(int i=0;i<n-1;i++)
    {
        ans%=mod;
        if(a[i]==-1)ans*=2;
        else
        {
            a[i]=find(a[i]);
            if(vis[a[i]])continue;
            vis[a[i]]=1;
            ans*=2;
        }
    }
    cout<<ans%mod;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 7812 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 8588 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 6264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 6264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 653 ms 8592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 654 ms 8720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 645 ms 8588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 8636 KB Output isn't correct
2 Halted 0 ms 0 KB -