Submission #468861

#	Time	Username	Problem	Language	Result	Execution time	Memory
468861		Cross_Ratio	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	154 ms	71704 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        int i;
        for(i=MAX/2-1;i>=1;i--) {
            seg[i] = seg[2*i] + seg[2*i+1];
        }
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
    }
    int sum(int s, int e) {
        return sum(s, e, 1, 0, MAX/2);
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = seg[2*n] + seg[2*n+1];
            n /= 2;
        }
    }
    void Minus(int n) {
        seg[n+MAX/2]--;
        update(n);
    }
};
vector<deque<int> > adj;
long long count_swaps(vector<int> S) {
    int N = S.size();
    N /= 2;
    adj.resize(N);
    int i;
    for(i=0;i< 2*N; i++) {
        if(S[i] > 0) adj[S[i]-1].push_back(i);
    }
    int cnt = 0;
    SegTree tree(2*N + 5);
    long long int pt = 0;
    for(i=0;i<2*N;i++) {
        if(S[i] < 0) {
            cnt += i + tree.sum(0, i);
            tree.Minus(i);
            pt++;
            int d = adj[-S[i]-1].front();
            adj[-S[i]-1].pop_front();
            cnt += d + tree.sum(0, d);
            tree.Minus(d);
            pt++;
        }
    }
    return cnt;
}

Compilation message (stderr)

shoes.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
shoes.cpp:22:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~

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