oj.uz

답안 #829893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829893 2023-08-18T15:38:18 Z Pajaraja Two Currencies (JOI23_currencies) C++17
100 / 100
 2624 ms 66428 KB 
#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 22
using namespace std;
long long bit[2][4*MAXN],y[MAXN],c[MAXN];
int in[2*MAXN],out[2*MAXN],vreme=1,u[MAXN],v[MAXN],p[MAXL][2*MAXN],f[MAXN],t[MAXN],x[MAXN],ans[MAXN],w,z[MAXN],n,m,q;
vector<int> g[2*MAXN],h[MAXN];
pair<int,int> pi[MAXN];
void upd(int k,int ind,long long s)
{
    while(ind<4*MAXN)
    {
        bit[k][ind]+=s;
        ind+=(ind&-ind);
    }
}
long long parc(int k,int ind)
{
    long long sum=0;
    while(ind)
    {
        sum+=bit[k][ind];
        ind-=(ind&-ind);
    }
    return sum;
}
long long range(int k, int l,int r) {return parc(k,r)-parc(k,l-1);}
void dfs(int s,int f)
{
    p[0][s]=f;
    in[s]=vreme++;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
    out[s]=vreme++;
}
bool insub(int a,int b) {return in[a]>=in[b] && out[a]<=out[b];} //jel a u podstablu od b
int lca(int a,int b)
{
    if(insub(a,b)) return b;
    if(insub(b,a)) return a;
    for(int i=MAXL-1;i>=0;i--) if(!insub(a,p[i][b])) b=p[i][b];
    return p[0][b];
}
long long query(int k,int a,int b)
{
    int c=lca(a,b);
    return range(k,in[c],in[a])+range(k,in[c],in[b]);
}
void answerqueries(int l,int r,vector<int> queries)
{
    int s=(l+r)/2;
    while(w<s)
    {
        w++;
        upd(0,in[n+w],c[w]);
        upd(0,out[n+w],-c[w]);
        upd(1,in[n+w],-1);
        upd(1,out[n+w],1);
    }
    while(w>s)
    {
        upd(0,in[n+w],-c[w]);
        upd(0,out[n+w],c[w]);
        upd(1,in[n+w],1);
        upd(1,out[n+w],-1);
        w--;
    }
    vector<int> q1,q2;
    for(int i=0;i<queries.size();i++)
    {
        int ind=queries[i];
        if(query(0,f[ind],t[ind])>y[ind]) q1.push_back(ind);
        else
        {
            q2.push_back(ind);
            ans[ind]=query(1,f[ind],t[ind]);
        }
    }
    if(l==r) return;
    answerqueries(l,s,q1);
    answerqueries(s+1,r,q2);
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<n;i++) cin>>u[i]>>v[i];
    for(int i=1;i<=m;i++) cin>>z[i]>>c[i];
    for(int i=1;i<=m;i++) pi[i]={c[i],z[i]};
    sort(pi+1,pi+m+1);
    for(int i=1;i<=m;i++) {c[i]=pi[i].first; z[i]=pi[i].second;}
    for(int i=1;i<n;i++) h[i].push_back(u[i]);
    for(int i=1;i<=m;i++) h[z[i]].push_back(n+i);
    for(int i=1;i<n;i++) h[i].push_back(v[i]);
    for(int i=1;i<n;i++) for(int j=0;j+1<h[i].size();j++)
    {
        g[h[i][j]].push_back(h[i][j+1]);
        g[h[i][j+1]].push_back(h[i][j]);
    }
    dfs(1,1);
    for(int j=1;j<MAXL;j++) for(int i=1;i<=n+m;i++) p[j][i]=p[j-1][p[j-1][i]];
    for(int i=1;i<=q;i++) cin>>f[i]>>t[i]>>x[i]>>y[i];
    for(int i=1;i<=m;i++)
    {
        upd(1,in[n+i],1);
        upd(1,out[n+i],-1);
    }
    vector<int> queries;
    for(int i=1;i<=q;i++) ans[i]=query(1,f[i],t[i]);
    for(int i=1;i<=q;i++) queries.push_back(i);
    answerqueries(1,m,queries);
    for(int i=1;i<=q;i++) cout<<max(x[i]-ans[i],-1)<<endl;
}

Compilation message

currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'void answerqueries(int, int, std::vector<int>)':
currencies.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<queries.size();i++)
      |                 ~^~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:93:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=1;i<n;i++) for(int j=0;j+1<h[i].size();j++)
      |                                      ~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7536 KB Output is correct
3 Correct 3 ms 7508 KB Output is correct
4 Correct 3 ms 7636 KB Output is correct
5 Correct 14 ms 8392 KB Output is correct
6 Correct 20 ms 8376 KB Output is correct
7 Correct 17 ms 8216 KB Output is correct
8 Correct 18 ms 8472 KB Output is correct
9 Correct 18 ms 8448 KB Output is correct
10 Correct 18 ms 8404 KB Output is correct
11 Correct 19 ms 8456 KB Output is correct
12 Correct 19 ms 8404 KB Output is correct
13 Correct 14 ms 8660 KB Output is correct
14 Correct 15 ms 8600 KB Output is correct
15 Correct 21 ms 8528 KB Output is correct
16 Correct 18 ms 8488 KB Output is correct
17 Correct 24 ms 8492 KB Output is correct
18 Correct 19 ms 8492 KB Output is correct
19 Correct 18 ms 8444 KB Output is correct
20 Correct 20 ms 8500 KB Output is correct
21 Correct 22 ms 8424 KB Output is correct
22 Correct 19 ms 8480 KB Output is correct
23 Correct 17 ms 8496 KB Output is correct
24 Correct 19 ms 8532 KB Output is correct
25 Correct 21 ms 8532 KB Output is correct
26 Correct 15 ms 8440 KB Output is correct
27 Correct 16 ms 8464 KB Output is correct
28 Correct 16 ms 8460 KB Output is correct
29 Correct 17 ms 8544 KB Output is correct
30 Correct 25 ms 8444 KB Output is correct
31 Correct 18 ms 8456 KB Output is correct
32 Correct 20 ms 8456 KB Output is correct
33 Correct 14 ms 8680 KB Output is correct
34 Correct 13 ms 8660 KB Output is correct
35 Correct 13 ms 8656 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7636 KB Output is correct
2 Correct 19 ms 8460 KB Output is correct
3 Correct 21 ms 8440 KB Output is correct
4 Correct 21 ms 8472 KB Output is correct
5 Correct 1967 ms 48748 KB Output is correct
6 Correct 2120 ms 48644 KB Output is correct
7 Correct 1867 ms 47140 KB Output is correct
8 Correct 1394 ms 44508 KB Output is correct
9 Correct 1272 ms 44788 KB Output is correct
10 Correct 2123 ms 53728 KB Output is correct
11 Correct 2154 ms 54056 KB Output is correct
12 Correct 2069 ms 54104 KB Output is correct
13 Correct 1966 ms 54176 KB Output is correct
14 Correct 1939 ms 53744 KB Output is correct
15 Correct 898 ms 65424 KB Output is correct
16 Correct 749 ms 66160 KB Output is correct
17 Correct 989 ms 64700 KB Output is correct
18 Correct 2287 ms 53968 KB Output is correct
19 Correct 2545 ms 53808 KB Output is correct
20 Correct 2591 ms 54032 KB Output is correct
21 Correct 2398 ms 56576 KB Output is correct
22 Correct 2482 ms 55304 KB Output is correct
23 Correct 2119 ms 55312 KB Output is correct
24 Correct 2159 ms 55556 KB Output is correct
25 Correct 1597 ms 55568 KB Output is correct
26 Correct 1560 ms 55796 KB Output is correct
27 Correct 1409 ms 55500 KB Output is correct
28 Correct 801 ms 53316 KB Output is correct
29 Correct 747 ms 54128 KB Output is correct
30 Correct 960 ms 53300 KB Output is correct
31 Correct 948 ms 53356 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 13 ms 8696 KB Output is correct
3 Correct 14 ms 8680 KB Output is correct
4 Correct 13 ms 8588 KB Output is correct
5 Correct 473 ms 53140 KB Output is correct
6 Correct 457 ms 52560 KB Output is correct
7 Correct 609 ms 55328 KB Output is correct
8 Correct 714 ms 66224 KB Output is correct
9 Correct 700 ms 66232 KB Output is correct
10 Correct 776 ms 66288 KB Output is correct
11 Correct 677 ms 66380 KB Output is correct
12 Correct 646 ms 66396 KB Output is correct
13 Correct 653 ms 66428 KB Output is correct
14 Correct 581 ms 66220 KB Output is correct
15 Correct 570 ms 66192 KB Output is correct
16 Correct 652 ms 66272 KB Output is correct
17 Correct 607 ms 66292 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7536 KB Output is correct
3 Correct 3 ms 7508 KB Output is correct
4 Correct 3 ms 7636 KB Output is correct
5 Correct 14 ms 8392 KB Output is correct
6 Correct 20 ms 8376 KB Output is correct
7 Correct 17 ms 8216 KB Output is correct
8 Correct 18 ms 8472 KB Output is correct
9 Correct 18 ms 8448 KB Output is correct
10 Correct 18 ms 8404 KB Output is correct
11 Correct 19 ms 8456 KB Output is correct
12 Correct 19 ms 8404 KB Output is correct
13 Correct 14 ms 8660 KB Output is correct
14 Correct 15 ms 8600 KB Output is correct
15 Correct 21 ms 8528 KB Output is correct
16 Correct 18 ms 8488 KB Output is correct
17 Correct 24 ms 8492 KB Output is correct
18 Correct 19 ms 8492 KB Output is correct
19 Correct 18 ms 8444 KB Output is correct
20 Correct 20 ms 8500 KB Output is correct
21 Correct 22 ms 8424 KB Output is correct
22 Correct 19 ms 8480 KB Output is correct
23 Correct 17 ms 8496 KB Output is correct
24 Correct 19 ms 8532 KB Output is correct
25 Correct 21 ms 8532 KB Output is correct
26 Correct 15 ms 8440 KB Output is correct
27 Correct 16 ms 8464 KB Output is correct
28 Correct 16 ms 8460 KB Output is correct
29 Correct 17 ms 8544 KB Output is correct
30 Correct 25 ms 8444 KB Output is correct
31 Correct 18 ms 8456 KB Output is correct
32 Correct 20 ms 8456 KB Output is correct
33 Correct 14 ms 8680 KB Output is correct
34 Correct 13 ms 8660 KB Output is correct
35 Correct 13 ms 8656 KB Output is correct
36 Correct 4 ms 7636 KB Output is correct
37 Correct 19 ms 8460 KB Output is correct
38 Correct 21 ms 8440 KB Output is correct
39 Correct 21 ms 8472 KB Output is correct
40 Correct 1967 ms 48748 KB Output is correct
41 Correct 2120 ms 48644 KB Output is correct
42 Correct 1867 ms 47140 KB Output is correct
43 Correct 1394 ms 44508 KB Output is correct
44 Correct 1272 ms 44788 KB Output is correct
45 Correct 2123 ms 53728 KB Output is correct
46 Correct 2154 ms 54056 KB Output is correct
47 Correct 2069 ms 54104 KB Output is correct
48 Correct 1966 ms 54176 KB Output is correct
49 Correct 1939 ms 53744 KB Output is correct
50 Correct 898 ms 65424 KB Output is correct
51 Correct 749 ms 66160 KB Output is correct
52 Correct 989 ms 64700 KB Output is correct
53 Correct 2287 ms 53968 KB Output is correct
54 Correct 2545 ms 53808 KB Output is correct
55 Correct 2591 ms 54032 KB Output is correct
56 Correct 2398 ms 56576 KB Output is correct
57 Correct 2482 ms 55304 KB Output is correct
58 Correct 2119 ms 55312 KB Output is correct
59 Correct 2159 ms 55556 KB Output is correct
60 Correct 1597 ms 55568 KB Output is correct
61 Correct 1560 ms 55796 KB Output is correct
62 Correct 1409 ms 55500 KB Output is correct
63 Correct 801 ms 53316 KB Output is correct
64 Correct 747 ms 54128 KB Output is correct
65 Correct 960 ms 53300 KB Output is correct
66 Correct 948 ms 53356 KB Output is correct
67 Correct 3 ms 7508 KB Output is correct
68 Correct 13 ms 8696 KB Output is correct
69 Correct 14 ms 8680 KB Output is correct
70 Correct 13 ms 8588 KB Output is correct
71 Correct 473 ms 53140 KB Output is correct
72 Correct 457 ms 52560 KB Output is correct
73 Correct 609 ms 55328 KB Output is correct
74 Correct 714 ms 66224 KB Output is correct
75 Correct 700 ms 66232 KB Output is correct
76 Correct 776 ms 66288 KB Output is correct
77 Correct 677 ms 66380 KB Output is correct
78 Correct 646 ms 66396 KB Output is correct
79 Correct 653 ms 66428 KB Output is correct
80 Correct 581 ms 66220 KB Output is correct
81 Correct 570 ms 66192 KB Output is correct
82 Correct 652 ms 66272 KB Output is correct
83 Correct 607 ms 66292 KB Output is correct
84 Correct 1413 ms 48568 KB Output is correct
85 Correct 1307 ms 42208 KB Output is correct
86 Correct 1296 ms 37376 KB Output is correct
87 Correct 2131 ms 51900 KB Output is correct
88 Correct 2067 ms 51904 KB Output is correct
89 Correct 2051 ms 51908 KB Output is correct
90 Correct 2124 ms 51836 KB Output is correct
91 Correct 2624 ms 51884 KB Output is correct
92 Correct 1474 ms 59148 KB Output is correct
93 Correct 1307 ms 61836 KB Output is correct
94 Correct 2515 ms 51696 KB Output is correct
95 Correct 2368 ms 51640 KB Output is correct
96 Correct 2417 ms 51632 KB Output is correct
97 Correct 2307 ms 51612 KB Output is correct
98 Correct 2082 ms 55132 KB Output is correct
99 Correct 2127 ms 55080 KB Output is correct
100 Correct 2102 ms 55168 KB Output is correct
101 Correct 2323 ms 55188 KB Output is correct
102 Correct 1546 ms 55248 KB Output is correct
103 Correct 1457 ms 55436 KB Output is correct
104 Correct 1520 ms 55444 KB Output is correct
105 Correct 815 ms 52500 KB Output is correct
106 Correct 766 ms 52720 KB Output is correct
107 Correct 936 ms 52928 KB Output is correct
108 Correct 969 ms 52680 KB Output is correct