oj.uz

답안 #962132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962132 2024-04-13T07:20:06 Z Ludissey Two Currencies (JOI23_currencies) C++14
30 / 100
 462 ms 29772 KB 
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

const int LOG=20;

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,m,q; cin >> n >> m >> q;
    vector<vector<pair<int,int>>> sum(n*2);
    vector<pair<int,int>> v;
    vector<int> ed;
    
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        ed.push_back(min(a-1,b-1));
    }
    for (int i = 0; i < m; i++){
        int p,c; cin >> p >> c;
        v.push_back({c,ed[p-1]});
    }
    vector<int> prefix(n*2);
    for (int i = 0; i < sz(v); i++)
    {
        if(i>0) prefix[i]+=prefix[i-1];
    }
    
    sort(v.begin(),v.end());
    for (int i = 0; i < m; i++){
        sum[v[i].second].push_back({v[i].first,i});
    }
    int square=sqrt(m)+2;
    int squareQ=sqrt(q)+2;
    vector<vector<pair<pair<pair<int,int>,pair<int,int>>,int>>> queries((q/squareQ)*2);
    vector<vector<int>> coins((q/squareQ)*2);
    vector<vector<int>> qrt((m/square)*2); 
    vector<int> qrtSUM((m/square)*2);
    vector<int> qrtCOUNT((m/square)*2);
    vector<int> ans(q);
    vector<pair<pair<int,int>,pair<int,int>>> copyQUERY(q);
    for (int Q = 0; Q < q; Q++)
    {
        int s,t,x,y; cin >> s >> t >> x >> y;
        copyQUERY[Q]={{s,t},{x,y}};
        prefix[s-1]++;
    }
    for (int i = 1; i < n; i++) prefix[i]+=prefix[i-1];
    
    for (int Q = 0; Q < q; Q++)
    {
        int s=copyQUERY[Q].first.first,t=copyQUERY[Q].first.second,x=copyQUERY[Q].second.first,y=copyQUERY[Q].second.second;
        if(s>t) swap(s,t);
        queries[(prefix[s-1]/squareQ)].push_back({{{t-1, s-1},{x,y}},Q});
    }
    for (int i = 0; i < sz(queries); i++) {
        sort(all(queries[i]));
    }
    for (int i = 0; i < sz(qrt); i++) qrt[i].resize(square+1);
    
    int l=-1,r=-1;
    int totalCOUNT=0;
    for (int i = 0; i < sz(queries); i++){
        for (int j = 0; j < sz(queries[i]); j++){
            int s=queries[i][j].first.first.second,t=queries[i][j].first.first.first,x=queries[i][j].first.second.first,y=queries[i][j].first.second.second,qr=queries[i][j].second;
            if(r==-1) {
                r=s;
                l=s;
            }
            for (int k = r; k < t; k++) {
                for (auto u : sum[k]) {
                    qrtSUM[(u.second/square)]+=u.first;
                    qrtCOUNT[(u.second/square)]++;
                    totalCOUNT++;
                    qrt[(u.second/square)][(u.second%square)]=u.first;
                }
            }
            for (int k = t; k < r; k++) {
                for (auto u : sum[k]) {
                    qrtSUM[(u.second/square)]-=u.first;
                    qrtCOUNT[(u.second/square)]--;
                    totalCOUNT--;
                    qrt[(u.second/square)][(u.second%square)]=0;
                }
            }
            for (int k = l; k < s; k++) {
                for (auto u : sum[k]) {
                    qrtSUM[(u.second/square)]-=u.first;
                    qrtCOUNT[(u.second/square)]--;
                    totalCOUNT--;
                    qrt[(u.second/square)][(u.second%square)]=0;
                }
            }
            for (int k = s; k < l; k++) {
                for (auto u : sum[k]) {
                    qrtSUM[(u.second/square)]+=u.first;
                    qrtCOUNT[(u.second/square)]++;
                    totalCOUNT++;
                    qrt[(u.second/square)][(u.second%square)]=u.first;
                }
            }
            int cqrt=0;
            int csum=0;
            int cnt=0;
            while(cqrt<sz(qrtSUM)){
                csum+=qrtSUM[cqrt];
                if(csum>y) break;
                cnt+=qrtCOUNT[cqrt];
                cqrt++;
            }
            if(cqrt==sz(qrtSUM)) {
                ans[qr]=x;
            }
            else {
                csum-=qrtSUM[cqrt];
                int _i=0;
                while(_i<sz(qrt[cqrt]))
                {
                    if(qrt[cqrt][_i]>0) cnt++;
                    csum+=qrt[cqrt][_i];
                    if(csum>y) {
                        cnt--;
                        break;
                    }
                    _i++;
                }
                ans[qr]=max(-1LL, x-(totalCOUNT-cnt));
            }
            l=s; r=t;
        }
    }
    for (int i = 0; i < sz(ans); i++) cout << ans[i] << "\n";
    
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 28.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 264 ms 17160 KB Output is correct
6 Correct 249 ms 16492 KB Output is correct
7 Correct 350 ms 21180 KB Output is correct
8 Correct 453 ms 28496 KB Output is correct
9 Correct 449 ms 28792 KB Output is correct
10 Correct 462 ms 28384 KB Output is correct
11 Correct 165 ms 27972 KB Output is correct
12 Correct 204 ms 28228 KB Output is correct
13 Correct 203 ms 27956 KB Output is correct
14 Correct 122 ms 29616 KB Output is correct
15 Correct 130 ms 28996 KB Output is correct
16 Correct 203 ms 29772 KB Output is correct
17 Correct 208 ms 29020 KB Output is correct

Subtask #4
0 / 32.0

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