oj.uz

Submission #412693

# Submission time Handle Problem Language Result Execution time Memory
412693 2021-05-27T11:03:17 Z 최서현(#7467) Loop Town (CCO21_day2problem3) C++17
0 / 25
 4 ms 588 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG

using namespace std;

int fen[1010101];
void upd(int pos)
{
    ++pos;
    while(pos < 1010101)
    {
        ++fen[pos];
        pos += pos & -pos;
    }
}
int qry(int pos)
{
    int ret = 0;
    while(pos)
    {
        ret += fen[pos];
        pos &= pos - 1;
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, L; cin >> n >> L;
    int X[n], Y[n];
    for(int i = 0; i < n; ++i) cin >> X[i] >> Y[i];
    vector<int> prX(X, X + n), prY(Y, Y + n);
    sort(prX.begin(), prX.end());
    sort(prY.begin(), prY.end());
    for(auto &i : X) i = lower_bound(prX.begin(), prX.end(), i) - prX.begin();
    for(auto &i : Y) i = lower_bound(prY.begin(), prY.end(), i) - prY.begin();
    int Z[n]; for(int i = 0; i < n; ++i) Z[Y[i]] = i;
    int A[n]; for(int i = 0; i < n; ++i) A[i] = Z[X[i]];
    int B[n]; for(int i = 0; i < n; ++i) B[A[i]] = i;

    #ifdef DEBUG
        cout << endl;
        cout << "A" << endl;
        for(auto i : A) cout << i << ' '; cout << endl;
        cout << endl;
    #endif

    long long inv = 0, ans = 0;
    for(int i = n - 1; i >= 0; --i)
    {
        inv += qry(B[i]);
        upd(B[i]);
    }
    ans = inv;

    for(int i = 0; i < n; ++i)
    {
        inv -= 2 * B[i] - n + 1;
        ans = min(ans, inv);
    }

    cout << ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 4 ms 588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 4 ms 588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 4 ms 588 KB Output isn't correct
4 Halted 0 ms 0 KB -