Submission #1032335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032335		Kipras	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	154 ms	284072 KiB

shoes

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxN = 1e5+10;

ll n;

ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
deque<ll> pos[maxN], neg[maxN];
ll used[maxN*2]={0};
ll ind = 0;

void build(ll v){

    if(v>=2*maxN){
        l[v]=ind;
        r[v]=ind;
        ind++;
        val[v]=0;
        lazy[v]=0;
    }else{
        build(v*2);
        build(v*2+1);
        l[v]=l[v*2];
        r[v]=r[v*2+1];
        val[v]=0;
        lazy[v]=0;
    }

}

void update(ll v, ll L, ll R, ll x){

    if(L>r[v]||R<l[v]){
        //cout<<"ending: "<<l[v]<<" "<<r[v]<<" "<<L<<" "<<R<<" "<<v<<"\n";
        return;
    }
    else if(L<=l[v]&&r[v]<=R){
        lazy[v]+=x;
        //cout<<"updation: "<<l[v]<<" "<<r[v]<<" "<<v<<"\n";
    }else{
        update(v*2, L, R, x);
        update(v*2+1, L, R, x);
    }

}

ll query(ll v, ll L, ll R){

    if(L>r[v]||R<l[v]){
        return 0;
    }
    else if(L<=l[v]&&r[v]<=R){
        val[v]+=lazy[v];
        lazy[v]=0;
        return val[v];
    }else{
        lazy[v*2]+=lazy[v];
        lazy[v*2+1]+=lazy[v];
        lazy[v]=0;
        return query(v*2, L, R)+query(v*2+1, L, R);
    }

}

ll count_swaps(vector<int> s){

    n = s.size();

    build(1);

    ll rez = 0;

    for(int i = 0; i < n; i++){
        if(s[i]>0)
            pos[s[i]].push_back(i);
        else
            neg[abs(s[i])].push_back(i);
    }

    for(int i = 0; i < n; i++){
        if(used[i])continue;

        ll v=abs(s[i]);
        if(s[i]>0){
            rez++;
            pos[v].pop_front();
            ll u = neg[v].front();
            neg[v].pop_front();
            ll p1 = i + query(1, i, i);
            ll p2 = u + query(1, u, u);
            update(1, i, u, 1);
            //cout<<rez<<" "<<i<<" "<<u<<" "<<p1<<" "<<p2<<" a\n";
            rez+=p2-p1-1;
            //cout<<rez<<"a\n";
            used[u]=1;
        }else{
            neg[v].pop_front();
            ll u = pos[v].front();
            pos[v].pop_front();
            ll p1 = i + query(1, i, i);
            ll p2 = u + query(1, u, u);
            update(1, i, u, 1);
            //cout<<rez<<" "<<i<<" "<<u<<" "<<p1<<" "<<p2<<" b\n";
            rez+=p2-p1-1;
            //cout<<rez<<"b\n";
            used[u]=1;
        }

    }

    return rez;

}

Compilation message (stderr)

shoes.cpp: In function 'void _Z5buildx.part.0(ll)':
shoes.cpp:19:12: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   19 |         l[v]=ind;
      |         ~~~^
shoes.cpp:11:17: note: while referencing 'l'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                 ^
shoes.cpp:20:12: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   20 |         r[v]=ind;
      |         ~~~^
shoes.cpp:11:28: note: while referencing 'r'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                            ^
shoes.cpp:22:14: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   22 |         val[v]=0;
      |         ~~~~~^
shoes.cpp:11:4: note: while referencing 'val'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |    ^~~
shoes.cpp:23:15: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   23 |         lazy[v]=0;
      |         ~~~~~~^
shoes.cpp:11:39: note: while referencing 'lazy'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                                       ^~~~
shoes.cpp:19:12: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   19 |         l[v]=ind;
      |         ~~~^
shoes.cpp:11:17: note: while referencing 'l'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                 ^
shoes.cpp:20:12: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   20 |         r[v]=ind;
      |         ~~~^
shoes.cpp:11:28: note: while referencing 'r'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                            ^
shoes.cpp:22:14: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   22 |         val[v]=0;
      |         ~~~~~^
shoes.cpp:11:4: note: while referencing 'val'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |    ^~~
shoes.cpp:23:15: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   23 |         lazy[v]=0;
      |         ~~~~~~^
shoes.cpp:11:39: note: while referencing 'lazy'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                                       ^~~~
shoes.cpp: In function 'void build(ll)':
shoes.cpp:19:12: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   19 |         l[v]=ind;
      |         ~~~^
shoes.cpp:11:17: note: while referencing 'l'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                 ^
shoes.cpp:20:12: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   20 |         r[v]=ind;
      |         ~~~^
shoes.cpp:11:28: note: while referencing 'r'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                            ^
shoes.cpp:22:14: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   22 |         val[v]=0;
      |         ~~~~~^
shoes.cpp:11:4: note: while referencing 'val'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |    ^~~
shoes.cpp:23:15: warning: array subscript 200020 is above array bounds of 'll [200020]' {aka 'long long int [200020]'} [-Warray-bounds]
   23 |         lazy[v]=0;
      |         ~~~~~~^
shoes.cpp:11:39: note: while referencing 'lazy'
   11 | ll val[maxN*2], l[maxN*2], r[maxN*2], lazy[maxN*2];
      |                                       ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15