fork download
copy 
  1.     #include<bits/stdc++.h>
  2.     using namespace std;
  3.     #include <ext/pb_ds/assoc_container.hpp>
  4.     #include <ext/pb_ds/tree_policy.hpp>
  5.     using namespace __gnu_pbds;
  6.     template <typename T>
  7.     using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;       //set
  8.     //  using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;  // multiset
  9.  
  10.     static int LOCAL=0;
  11.  
  12.     #define length(a) (sizeof(a)/sizeof(a[0]))
  13.     #define print(v,i,x) for(int j=i;j<=x;j++){cout<<v[j]<<" ";}cout<<endl;
  14.     #define pb push_back
  15.     #define mp make_pair
  16.     #define lli long long int
  17.     #define ulli unsigned long long int
  18.     #define all(x) x.begin(),x.end()
  19.     #define sz(x) ((int)x.size())
  20.     #define f first
  21.     #define s second
  22.  
  23.     #define si(x) scanf("%d",&x)
  24.     #define slli(x) scanf("%lld",&x)
  25.     #define si2(x,y) scanf("%d %d",&x,&y)
  26.     #define si3(x,y,z) scanf("%d %d %d",&x,&y,&z)
  27.     #define slli2(x,y) scanf("%lld %lld",&x,&y)
  28.     #define slli3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
  29.  
  30.     #define pi(x) printf("%d",x)
  31.     #define pi2(x,y) printf("%d %d",x,y)
  32.     #define pi3(x,y,z) printf("%d %d %d",x,y,z)
  33.     #define pli(x) printf("%ld",x)
  34.     #define plli(x) printf("%lld",x)
  35.     #define plli2(x,y) printf("%lld %lld",x,y)
  36.     #define plli3(x,y,z) printf("%lld %lld %lld",x,y,z)
  37.     #define pn printf("\n")
  38.     #define ps printf(" ")
  39.     #define pc(c) printf("%c",c)
  40.     #define pstr(s) printf("%s",s)
  41.  
  42.     #define FOR(i,x,n) for(int i=x;i<=n;i++)
  43.     #define FORl(i,x,n) for(lli i=x;i<=n;i++)
  44.     #define ROF(i,x,n) for(int i=x;i>=n;i--)
  45.     #define ROFl(i,x,n) for(lli i=x;i>=n;i--)
  46.  
  47.     #define debug(x) cout << "  - " << #x << ": " << x << endl;
  48.     #define debugs(x, y) cout << "  - " << #x << ": " << x << "         " << #y << ": " << y << endl;
  49.     #define debugss(x, y, z) cout << "  - " << #x << ": " << x << "         " << #y << ": " << y << "         " << #z << ": " << z <<  endl;
  50.     #define fastIO 	std::ios::sync_with_stdio(false);cin.tie(NULL);
  51.     #define cut cout<<"------------------------------------------\n";
  52.     #define cut1 cout<<"******************************************\n";
  53.  
  54.     typedef vector<int> vi;
  55.     typedef vector<long long> vlli;
  56.     typedef vector<string> vstr;
  57.  
  58.     typedef pair<int,int> prii;
  59.     typedef pair<int,lli> prilli;
  60.     typedef pair<lli,int> prllii;
  61.     typedef pair<lli,lli> prllilli;
  62.  
  63.     const lli mod = 1000000007ll;
  64.     const lli MOD = 1000000009ll;
  65.     const lli INF = LLONG_MAX/10;
  66.     const int inf = INT_MAX/2;
  67.  
  68.     lli count_bit(lli _x){lli _ret=0;while(_x){if(_x%2==1)_ret++;_x/=2;}return _ret;}
  69.     bool check_bit(lli _mask,lli _i){lli x=1;return (_mask&(x<<_i))==0?false:true;}
  70.     lli set_bit(lli _mask,lli _i){lli x=1;_mask=_mask|(x<<_i);return _mask;}
  71.     lli msb(lli _mask){lli ret=-1;int cnt=0;while(_mask){if(_mask&1)ret=cnt;_mask/=2;cnt++;}return ret;}
  72.     lli powermod(lli _a,lli _b,lli _m=mod){lli _r=1;while(_b){if(_b%2==1)_r=(_r*_a)%_m;_b/=2;_a=(_a*_a)%_m;}return _r;}
  73.     lli power(lli _a,lli _b){lli _r=1;while(_b){if(_b%2==1)_r=(_r*_a);_b/=2;_a=(_a*_a);}return _r;}
  74.     lli add(lli a,lli b,lli m=mod){lli x=a+b;while(x>=m)x-=m;return x;}
  75.     lli sub(lli a,lli b,lli m=mod){lli x=a-b;while(x<0)x+=m;return x;}
  76.     lli mul(lli a,lli b,lli m=mod){lli x=a*b;x%=m;return x;}
  77.     lli gcd(lli a,lli b){while(a&&b)a>b?a%=b:b%=a;return a+b;}
  78.     lli lcm(lli a,lli b){return (max(a,b)/gcd(a,b))*min(a,b);}
  79.  
  80.     struct pair_hash {
  81.         std::size_t operator () (const std::pair<lli,lli> &p) const {
  82.             auto h1 = std::hash<lli>{}(p.first);
  83.             auto h2 = std::hash<lli>{}(p.second);
  84.             return h1 ^ h2;
  85.         }
  86.     };
  87.  
  88.     struct cmp{
  89.         bool operator()(prii const & l,prii const & r){
  90.            return l.s<r.s;
  91.         }
  92.     }myobject;
  93.  
  94.     ordered_set<int> tr[800010];
  95.     int a[200010],n,q,l,r;
  96.  
  97.     void build(int node,int st,int en){
  98.         if(st==en){
  99.             tr[node].insert(st);
  100.             return;
  101.         }
  102.         int mid=(st+en)>>1;
  103.         build(2*node,st,mid);
  104.         build(2*node+1,mid+1,en);
  105.         FOR(i,st,en)tr[node].insert(i);
  106.     }
  107.  
  108.     void update(int node,int st,int en,int idx,int val){
  109.         if(st==en){
  110.             tr[node].erase(a[idx]);
  111.             tr[node].insert(val);
  112.             return;
  113.         }
  114.         int mid=(st+en)>>1;
  115.         if(idx<=mid)
  116.             update(2*node,st,mid,idx,val);
  117.         else
  118.             update(2*node+1,mid+1,en,idx,val);
  119.  
  120.         tr[node].erase(a[idx]);
  121.         tr[node].insert(val);
  122.     }
  123.  
  124.     lli query(int node,int st,int en,int l,int r,int val){
  125.         if(en<l || st>r || l>r)return 0;
  126.  
  127.         if(st>=l && en<=r)
  128.         return tr[node].order_of_key(val);
  129.  
  130.         int mid=(st+en)>>1;
  131.         return query(2*node,st,mid,l,r,val)+query(2*node+1,mid+1,en,l,r,val);
  132.     }
  133.  
  134.     int main()
  135.     {
  136.  
  137.         LOCAL=0;
  138.         if(LOCAL){
  139.             freopen("C:\\Users\\Smit Patel\\Downloads\\D-large.in","r",stdin);
  140.             freopen("C:\\Users\\Smit Patel\\Desktop\\out.txt","w",stdout);
  141.         }
  142.  
  143.         FOR(i,1,200000)a[i]=i;
  144.  
  145.         si2(n,q);
  146.  
  147.         build(1,1,n);
  148.  
  149.         lli ans=0;
  150.         while(q--){
  151.             si2(l,r);
  152.             if(l>r)swap(l,r);
  153.             if(l==r)goto out;
  154.             ans-=r-l-1-query(1,1,n,l+1,r-1,a[r]);
  155.             ans-=query(1,1,n,l+1,r,a[l]);
  156.             update(1,1,n,l,a[r]);
  157.             update(1,1,n,r,a[l]);
  158.             swap(a[l],a[r]);
  159.             ans+=r-l-1-query(1,1,n,l+1,r-1,a[r]);
  160.             ans+=query(1,1,n,l+1,r,a[l]);
  161.             out:
  162.             plli(ans);pn;
  163.         }
  164.  
  165.         return 0;
  166.     }
  167.  
Success #stdin #stdout 0.03s 78720KB
comments (?)
stdin
copy 
2 1
1 2
stdout
copy 
1
https://ideone.com/500vNF
language:
C++14 (gcc 8.3)
created:
7 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!