제출 #182280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
182280		PedroBigMan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	947 ms	36332 KiB

shoes

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include "shoes.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF 100000000000000000LL
int insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}

class ST
{
    public:
    ll N; vector<ll> ar; vector<ll> p;
    ll neut;
    
    ll op(ll a, ll b)
    {
        return (a+b);
    }
    
    ST(vector<ll> arr)
    {
        neut=0;
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,arr.size()) {ar.pb(arr[i]);} 
        REP(i,arr.size(),N) {ar.pb(neut);}
        REP(i,0,N) {p.pb(0);}
        REP(i,0,N) {p.pb(ar[i]);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=op(p[2*cur],p[2*cur+1]);
            cur--;
        }
    }
    
    ll query(ll a,ll b, ll c, ll x, ll y) //c=current node, starting in 1, a,b=range of query, x,y=range of node c in the array down, x,y from 0 to N-1. query(a,b)->query(a,b,1,0,N-1)
    {
        if(y<a || x>b) {return neut;}
        if(x>=a && y<=b) {return p[c];}
        ll mid=(x+y)/2;
        return op(query(a,b,2*c,x,mid),query(a,b,2*c+1,mid+1,y));
    }
    
    void update(ll s, ll a, ll c, ll x, ll y) //positions in [a,b] from 0 to N-1 gets +s
    {
        if(y<a || x>a) {return ;}
        p[c]+=s;
        if(c==a+N) {ar[a]+=s; return;}
        ll mid=(x+y)/2;
        update(s,a,2*c,x,mid); update(s,a,2*c+1,mid+1,y);
    }
};

ll count_swaps(vector<int> s) 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N=s.size()/2;
    map<ll,vector<ll> > m;
    vector<ll> xx; 
    REP(i,0,2*N)
    {
        if(m.find(s[i])==m.end()) {m[s[i]]=xx;}
        m[s[i]].pb(i);
    }
    ll ind=0; ll ans=0;
    REP(i,0,2*N)
    {
        if(m.find(i)==m.end()) {continue;}
        REP(j,0,m[i].size())
        {
            if(m[i][j]<m[-i][j]) {ans++;}
            s[m[i][j]]=ind;
            s[m[-i][j]]=ind;
            ind++;
        }
    }
    map<ll,ll> t;
    ind=0;
    REP(i,0,2*N)
    {
        if(t.find(s[i])==t.end()) {t[s[i]]=ind; ind++;}
    }
    REP(i,0,2*N) {s[i]=t[s[i]];}
    vector<ll> x; REP(i,0,N) {x.pb(0LL);}
    ST S(x);
    REP(i,0,2*N)
    {
        ans+=S.query(s[i]+1,S.N-1,1,0,S.N-1);
        S.update(1,s[i],1,0,S.N-1);
    }
    return ans;
}

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