fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,q,st[36][400005],lz[36][400005];
  5. string s;
  6. void UPDATE(int i, int id, int l, int r, int u, int v, int x)
  7. {
  8.     if (l>v || r<u) return;
  9.     else if (l>=u && r<=v)
  10.     {
  11.         st[i][id]=x*(r-l+1),lz[i][id]=x;
  12.         return;
  13.     }
  14.     int mid=(l+r)/2;
  15.     if (lz[i][id]!=-1)
  16.     {
  17.         st[i][id*2]=lz[i][id]*(mid-l+1),lz[i][id*2]=lz[i][id];
  18.         st[i][id*2+1]=lz[i][id]*(r-mid),lz[i][id*2+1]=lz[i][id],lz[i][id]=-1;
  19.     }
  20.     UPDATE(i,id*2,l,mid,u,v,x),UPDATE(i,id*2+1,mid+1,r,u,v,x);
  21.     st[i][id]=st[i][id*2]+st[i][id*2+1];
  22. }
  23. int GET(int i, int id, int l, int r, int u, int v)
  24. {
  25.     if (l>v || r<u) return 0;
  26.     else if (l>=u && r<=v) return st[i][id];
  27.     int mid=(l+r)/2;
  28.     if (lz[i][id]!=-1)
  29.     {
  30.         st[i][id*2]=lz[i][id]*(mid-l+1),lz[i][id*2]=lz[i][id];
  31.         st[i][id*2+1]=lz[i][id]*(r-mid),lz[i][id*2+1]=lz[i][id],lz[i][id]=-1;
  32.     }
  33.     return GET(i,id*2,l,mid,u,v)+GET(i,id*2+1,mid+1,r,u,v);
  34. }
  35. signed main()
  36. {
  37.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  38.     cin>>n>>q>>s;
  39.     s="0"+s;
  40.     for (int i=1;i<=4*n;i++) for (int j='a';j<='z';j++) lz[j-96][i]=-1;
  41.     for (int i=1;i<=n;i++) UPDATE(s[i]-96,1,1,n,i,i,1);
  42.     for (int i=1;i<=q;i++)
  43.     {
  44.         int l,r,k;
  45.         cin>>l>>r>>k;
  46.         if (k==1)
  47.         {
  48.             int u=l,cnt[36];
  49.             for (int j='a';j<='z';j++) cnt[j-96]=GET(j-96,1,1,n,l,r);
  50.             for (int j='a';j<='z';j++) if (cnt[j-96]) UPDATE(j-96,1,1,n,l,r,0),UPDATE(j-96,1,1,n,u,u+cnt[j-96]-1,1),u+=cnt[j-96];
  51.         }
  52.         else 
  53.         {
  54.             int u=l,cnt[36];
  55.             for (int j='z';j>='a';j--) cnt[j-96]=GET(j-96,1,1,n,l,r);
  56.             for (int j='z';j>='a';j--) if (cnt[j-96]) UPDATE(j-96,1,1,n,l,r,0),UPDATE(j-96,1,1,n,u,u+cnt[j-96]-1,1),u+=cnt[j-96];
  57.         }
  58.     }
  59.     for (int i=1;i<=n;i++) for (int j='a';j<='z';j++) if (GET(j-96,1,1,n,i,i)==1) 
  60.     {
  61.         cout<<(char) j;
  62.         break;
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lpO2J2
language:
C++14 (gcc 8.3)
created:
2 days 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!