oj.uz

답안 #971446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971446 2024-04-28T14:08:08 Z andro Examination (JOI19_examination) C++14
20 / 100
 98 ms 19556 KB 
#include <bits/stdc++.h>.

#define int long long

using namespace std;

const int N = 2e5 + 5;

struct fenw {
    int t[N];
    void add(int i, int val){
        for(; i < N; i += i & - i) {
            t[i] += val;
        }
    }
    int query(int i) {
        int ans = 0;
        for(; i > 0; i -= i & - i) {
            ans += t[i];
        }
        return ans;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}fenw1, fenw2;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<pair<int,int>> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        a[i].first += 1;
        a[i].second += 1;
    }
    sort(a.begin() + 1, a.end());
    //cout << "\n";
    for(int i = 1; i <= n; i++) {
        //cout << a[i].first << " " << a[i].second << "\n";
    }
    //cout << "\n";
    vector<pair<int,int>> query1[n + 1];
    vector<pair<int,int>> saberi2[n + 1];
    vector<pair<int,int>> oduzmi2[n + 1];
    int index = 1;
    vector<int> ans(q + 1, 0);
    while(q--) {
        int x, y, z;
        cin >> x >> y >> z;
        x += 1;
        y += 1;
        z += 1;
        int l = 1, r = n, p = - 1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[mid].first >= x) {
                r = mid - 1;
                p = mid;
            }
            else {
                l = mid + 1;
            }
        }
        if(p == - 1) {
            index += 1;
            continue;
        }
        /*
        int ans = 0;
        for(int i = p; i <= n; i++) {
            if(a[i].second >= max(z - a[i].first, y)) {
                ans += 1;
            }
        }
        cout << ans << "\n";*/
        //query[p].push_back({{y, z}, index++});
        l = p, r = n; int g = - 1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(z - a[mid].first >= y) {
                l = mid + 1;
                g = mid;
            }
            else {
                r = mid - 1;
            }
        }
        int ans = 0;
        //cout << index << " " << p << " " << g << "\n";
        if(g == - 1) {
            /*
            for(int i = p; i <= n; i++) {
                if(a[i].second >= y) {
                    ans += 1;
                }
            }*/
            query1[p].push_back({y, index++});
        }
        else {
            /*
            for(int i = p; i <= g; i++) {
                if(a[i].first + a[i].second >= z) {
                    ans += 1;
                }
            }*/
            saberi2[p].push_back({z, index});
            if(g + 1 <= n )
                oduzmi2[g + 1].push_back({z, index});
            /*
            for(int i = g + 1; i <= n; i++) {
                if(a[i].second >= y) {
                    ans += 1;
                }
            }*/
            if(g + 1 <= n) {
                query1[g + 1].push_back({y, index++});
            }
            else {
                index += 1;
            }
        }
    }
    for(int i = n; i > 0; i--) {
        fenw1.add(a[i].second, 1);
        fenw2.add(a[i].first + a[i].second, 1);
        for(auto it : query1[i]) {
            ans[it.second] += fenw1.query(it.first, N - 1);
            /*
            for(int j = i; j <= n; j += 1) {
                if(a[j].second >= it.first) {
                    ans[it.second] += 1;
                }
            }*/
        }
        for(auto it : saberi2[i]) {
            ans[it.second] += fenw2.query(it.first, N - 1);
            /*
            for(int j = i; j <= n; j += 1) {
                if(a[j].first + a[j].second >= it.first) {
                    ans[it.second] += 1;
                }
            }*/
        }
        for(auto it : oduzmi2[i]) {
            ans[it.second] -= fenw2.query(it.first, N - 1);
            /*
            for(int j = i; j <= n; j += 1) {
                if(a[j].first + a[j].second >= it.first) {
                    ans[it.second] -= 1;
                }
            }*/
        }
    }
    for(int i = 1; i < index; i++) {
        cout << ans[i] << "\n";
    }
}

Compilation message

examination.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>.
      |                         ^
examination.cpp: In function 'int main()':
examination.cpp:91:13: warning: unused variable 'ans' [-Wunused-variable]
   91 |         int ans = 0;
      |             ^~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 17744 KB Output is correct
2 Correct 74 ms 17744 KB Output is correct
3 Correct 73 ms 17748 KB Output is correct
4 Correct 70 ms 16772 KB Output is correct
5 Correct 53 ms 16500 KB Output is correct
6 Correct 46 ms 15400 KB Output is correct
7 Correct 65 ms 17492 KB Output is correct
8 Correct 72 ms 17772 KB Output is correct
9 Correct 64 ms 17488 KB Output is correct
10 Correct 48 ms 15028 KB Output is correct
11 Correct 81 ms 16660 KB Output is correct
12 Correct 37 ms 13532 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 17744 KB Output is correct
2 Correct 74 ms 17744 KB Output is correct
3 Correct 73 ms 17748 KB Output is correct
4 Correct 70 ms 16772 KB Output is correct
5 Correct 53 ms 16500 KB Output is correct
6 Correct 46 ms 15400 KB Output is correct
7 Correct 65 ms 17492 KB Output is correct
8 Correct 72 ms 17772 KB Output is correct
9 Correct 64 ms 17488 KB Output is correct
10 Correct 48 ms 15028 KB Output is correct
11 Correct 81 ms 16660 KB Output is correct
12 Correct 37 ms 13532 KB Output is correct
13 Incorrect 98 ms 19556 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -