fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define scl(n) scanf("%d",&n)
  4. #define ll int
  5.  
  6. int dsu[302][115000],ara[100005],nxt[302],track[302][10002];
  7.  
  8. int fnd(ll a,ll b)
  9. {
  10.     if(dsu[a][b]<=1e4)
  11.         return b;
  12.     return dsu[a][b]=fnd(a,dsu[a][b]);
  13. }
  14.  
  15. int main()
  16. {
  17.     //freopen("input16.txt","r",stdin);
  18.     //freopen("output16.txt","w",stdout);
  19.     int n,m,i,j,k,a,b,c,x,y,z,l,r,p,q,sz=340;
  20.     scl(n);
  21.     for(i=0;i<=300;i++){
  22.         nxt[i]=10000+340+1;
  23.     }
  24.     for(i=1;i<=n;i++){
  25.         scl(ara[i]);
  26.         a=i/sz;
  27.         b=i%sz;
  28.         b++;
  29.         b+=1e4;
  30.         c=ara[i];
  31.         if(track[a][c]==0){
  32.             track[a][c]=nxt[a];
  33.             dsu[a][nxt[a]]=c;
  34.             nxt[a]++;
  35.         }
  36.         dsu[a][b]=track[a][c];
  37.     }
  38.     ll qq;
  39.     scl(qq);
  40.     ll t;
  41.     for(t=1;t<=qq;t++)
  42.     {
  43.         scl(l);
  44.         scl(r);
  45.         scl(p);
  46.         scl(q);
  47.         if(p==q){
  48.             continue;
  49.         }
  50.         //cout<<t<< " "<<l<< " " <<r<< " " <<p<< " " <<q<<endl;
  51.         x=l/sz;
  52.         y=r/sz;
  53.         if(track[x][q]==0 || track[y][q]==0)
  54.         {
  55.             if(track[x][q]==0){
  56.                 track[x][q]=nxt[x];
  57.                 dsu[x][nxt[x]]=q;
  58.                 nxt[x]++;
  59.             }
  60.             if(track[y][q]==0){
  61.                 track[y][q]=nxt[y];
  62.                 dsu[y][nxt[y]]=q;
  63.                 nxt[y]++;
  64.             }
  65.             //nxt++;
  66.         }
  67.         for(i=l;i<=r && i/sz==x && i<=n;i++)
  68.         {
  69.             k=i%sz;
  70.             k+=10001;
  71.             a=fnd(x,k);
  72.             b=dsu[x][a];
  73.             if(b!=p)
  74.                 continue;
  75.             dsu[x][k]=track[x][q];
  76.  
  77.  
  78.         }
  79.         //cout<<t<< " " <<qq<<endl;
  80.         if(x==y)
  81.             continue;
  82.  
  83.         for(i=r;i>0 && i/sz==y;i--)
  84.         {
  85.             k=i%sz;
  86.             k+=10001;
  87.             a=fnd(y,k);
  88.             b=dsu[y][a];
  89.             if(b!=p)
  90.                 continue;
  91.             dsu[y][k]=track[y][q];
  92.         }
  93.  
  94.         for(i=x+1;i<y;i++)
  95.         {
  96.             if(track[i][p]==0)
  97.                 continue;
  98.             a=track[i][p];
  99.             b=track[i][q];
  100.             if(b==0){
  101.                 track[i][q]=a;
  102.                 dsu[i][a]=q;
  103.             }
  104.             else{
  105.                 dsu[i][a]=b;
  106.             }
  107.             track[i][p]=0;
  108.         }
  109.         //cout<<t<<"   "<<q<<endl;
  110.     }
  111.  
  112.     for(i=1;i<=n;i++)
  113.     {
  114.         a=i/sz;
  115.         b=i%sz;
  116.         b+=10001;
  117.         c=fnd(a,b);
  118.         c=dsu[a][c];
  119.         printf("%d",c);
  120.         if(i<n)
  121.             printf(" ");
  122.     }
  123.     cout<<endl;
  124.  
  125. }
  126.  
Runtime error #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ydNCyS
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!