oj.uz

답안 #477819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477819 2021-10-04T02:34:23 Z Mike4235 Examination (JOI19_examination) C++17
0 / 100
 967 ms 41744 KB 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

struct Point{
    int x, y, z, id, ans;
    bool operator< (Point const& o) {
        if (x != o.x) return x > o.x;
        if (y != o.y) return y > o.y;
        return z > o.z;
    }
};

const int k = 6e5;

int n, q;
map<int, int> mp;
int res[100005], fentree[600005];
vector<Point> v, s;

void update(int i, int val) {
    for (; i <= k; i += i & -i) fentree[i] += val;
}

int get(int i) {
    int res = 0;
    for (; i; i -= i & -i) res += fentree[i];
    return res;
}

void cdq(int l, int r, vector<Point>& v) {
    if (l == r) return;
    int m = (l + r)/2;
    cdq(l, m, v); cdq(m + 1, r, v);

    // cout << l << " " << r << "\n";
    // for1(i,l,r) cout << v[i].x << " " << v[i].y << " " << v[i].z << "\n";
    vector<Point> st;
    vector<int> roll;
    int a = l, b = m + 1, sum = 0;

    while (a <= m && b <= r) {
        if (v[a].y > v[b].y) {
            sum++;
            update(v[a].z, 1);
            roll.push_back(v[a].z);
            st.push_back(v[a++]);
        }
        else {
            v[b].ans += sum - get(v[b].z);
            // cout << v[b].x << " " << v[b].y << " " << v[b].z << " " << v[b].id << " " << sum - get(v[b].z) << "\n";
            st.push_back(v[b++]);
        }
    }

    while (a <= m) st.push_back(v[a++]);
    while (b <= r) {
        v[b].ans += sum - get(v[b].z);
        // cout << v[b].x << " " << v[b].y << " " << v[b].z << " " << v[b].id << " " << sum - get(v[b].z) << "\n";
        st.push_back(v[b++]);
    }
    // cout << "\n";

    for1(i,l,r) v[i] = st[i - l];
    for (auto x : roll) update(x, -1);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> q;
    for1(i,1,n) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b, a + b, 0, 0});
        mp[a] = 0;
        mp[b] = 0;
        mp[a + b] = 0;
    }

    for1(i,1,q) {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--; z--;
        v.push_back({x, y, z, i, 0});
        s.push_back({x, y, z, i, 0});
        mp[x] = 0;
        mp[y] = 0;
        mp[z] = 0;
    }

    int cur = 0;
    for (auto &p : mp) p.second = ++cur;
    for (auto &p : v) p.x = mp[p.x], p.y = mp[p.y], p.z = mp[p.z];
    for (auto &p : s) p.x = mp[p.x], p.y = mp[p.y], p.z = mp[p.z];

    sort(v.begin(), v.end());
    sort(s.begin(), s.end());

    cdq(0, n + q - 1, v);
    cdq(0, q - 1, s);

    // for (auto p : v) cout << p.x << " " << p.y << " " << p.z << " " << p.id << " " << p.ans << "\n";
    // cout << "\n";
    // for (auto p : s) cout << p.x << " " << p.y << " " << p.z << " " << p.id << " " << p.ans << "\n";
    // cout << "\n";

    for (auto p : v) if (p.id) res[p.id] += p.ans;
    for (auto p : s) res[p.id] -= p.ans;

    for1(i,1,q) cout << res[i] << "\n";
    
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 967 ms 41744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 967 ms 41744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -