oj.uz

답안 #961808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961808 2024-04-12T13:33:08 Z Ludissey Two Currencies (JOI23_currencies) C++14
0 / 100
 5000 ms 22364 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);
    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]});
    }
    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*3)+2;
    int squareN=sqrt(n*3)+2;
    vector<int> qrs(m);
    vector<vector<pair<pair<pair<int,int>,pair<int,int>>,int>>> queries((n/squareN)+1);
    vector<vector<int>> coins((n/squareN)+1);
    vector<vector<int>> qrt((m/square)+1); 
    vector<int> qrtSUM((m/square)+1);
    vector<int> qrtCOUNT((m/square)+1);
    vector<int> ans(q);
    for (int Q = 0; Q < q; Q++)
    {
        int s,t,x,y; cin >> s >> t >> x >> y;
        if(s>t) swap(s,t);
        queries[(s/squareN)].push_back({{{t-1, s-1},{x,y}},Q});
        coins[(s/squareN)].push_back(y);
    }
    for (int i = 0; i < sz(queries); i++) {
        sort(all(queries[i]));
        sort(all(coins[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 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

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

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 776 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 238 ms 12236 KB Output is correct
6 Correct 216 ms 11720 KB Output is correct
7 Correct 314 ms 17128 KB Output is correct
8 Correct 404 ms 22352 KB Output is correct
9 Correct 387 ms 22312 KB Output is correct
10 Correct 385 ms 22364 KB Output is correct
11 Execution timed out 5048 ms 21580 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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