Submission #534055

#	Time	Username	Problem	Language	Result	Execution time	Memory
534055		Bogdan1110	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	117 ms	49188 KiB

shoes

#include <bits/stdc++.h>
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<ld, null_type,less<ld>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element

void files() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

const double eps = 0.00000001;
const int NMAX = 60;
const ll inf = LLONG_MAX/2;
const ll modi = 998244353;

map<int,vector<int> >mapa;
int seg[NMAX*4];
map<int,int> pret;

int qu(int sl, int sr, int l, int r, int node) {
    if ( sr < l || sl > r ) return 0;
    if ( sr >= r && sl <= l ) return seg[node];
    int mid = l+r;
    mid /=2;
    return qu(sl,sr,l,mid,node*2+1) + qu(sl,sr,mid+1,r,node*2+2);
}

void upd(int i, int l, int r, int node) {
    if ( r < i || l > i ) return;
    //cout << i << ' ' << l << ' ' << r << ' ' << node << endl ;
    if ( l == r ) {
        seg[node] = 1;
        return;
    }
    int mid = l+r;
    mid /=2;
    upd(i,mid+1,r,node*2+2);
    upd(i,l,mid,node*2+1);
    seg[node] = seg[node*2+1] + seg[2*node+2];
}

ll count_swaps(vector<int>v) {
    int n = v.size();
    for (int i = 0 ; i < n; i++ ) {
        mapa[v[i]].pb(i);
    }
    ll ans = 0;
    for (int i = 0 ; i < n ; i++ ) {
        if ( qu(i,i,0,n,0) ) continue;
        int gde = mapa[-v[i]][upper_bound(all(mapa[-v[i]]), max(pret[-v[i]],i))-mapa[-v[i]].begin()];
        //cout << "!" << i << ' ' << gde  << ' ' << v[i] << endl;
        int q = qu(i,gde,0,n,0);
        //cout << q << endl ;
        pret[-v[i]] = gde;
        //for(auto u : pret) cout << u.fi << ':' << u.se << endl ;
        upd(gde,0,n,0);
        ll res = gde-i-1 + (v[i] < v[gde]?0:1) - q;
        ans += res;
    }
    return ans;
}

void solve () {
    int n;
    cin >> n;
    vector<int>v(n*2);
    for (int i = 0 ; i < n*2 ; i++ ) {
        cin >> v[i];
    }
    cout << count_swaps(v) << endl;
}

Compilation message (stderr)

shoes.cpp: In function 'void files()':
shoes.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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