Submission #1037777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1037777	2024-07-29T08:15:48 Z	변재우(#10984)	Tourism (JOI23_tourism)	C++17	7 / 100	92 ms	5904 KB

tourism

// #include <bits/stdc++.h>
// using namespace std;

// const int Nmax=100010, sqrtN=500;
// int N, M, Q, C[Nmax], p, L[Nmax], R[Nmax], D[Nmax], P[20][Nmax];
// int curr, par, cnt[Nmax], ans[Nmax];
// set<int> V;
// vector<int> adj[Nmax];
// struct Query {int l, r, i;}X[Nmax];

// int LCA(int u, int v) {
//     if(!u || !v) return 0;
//     if(D[u]<D[v]) swap(u, v);
//     for(int i=16; i>=0; i--) if(D[P[i][u]]>D[v]) u=P[i][u];
//     if(D[u]!=D[v]) u=P[0][u];
//     for(int i=16; i>=0; i--) if(P[i][u]!=P[i][v]) u=P[i][u], v=P[i][v];
//     if(u!=v) u=P[0][u];
//     return u;
// }

// class LSeg {
// public:
//     void Init() {
//         for(int i=1; i<=M; i++) lx[0][i]=rx[0][i]=C[i];
//         for(int i=1; i<=16; i++) {
//             for(int j=1; j<=M; j++) {
//                 if(j+(1<<(i-1))<=M) lx[i][j]=LCA(lx[i-1][j], lx[i-1][j+(1<<(i-1))]);
//                 if(j-(1<<(i-1))>=1) rx[i][j]=LCA(rx[i-1][j], rx[i-1][j-(1<<(i-1))]);
//             }
//         }
//     }
//     int Query(int l, int r) {
//         int t=(31-__builtin_clz(r-l+1));
//         return LCA(lx[t][l], rx[t][r]);
//     }
// private:
//     int lx[20][Nmax], rx[20][Nmax];
// }TL;

// void DFS(int curr, int prev) {
//     L[curr]=++p;
//     for(int next:adj[curr]) if(next!=prev) D[next]=D[curr]+1, P[0][next]=curr, DFS(next, curr);
//     R[curr]=p;
// }

// set<pair<int, int>> DFS2(int curr, int prev) {
//     set<pair<int, int>> ret;
//     for(int next:adj[curr]) if(next!=prev) {

//     }
// }

// signed main() {
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     cin>>N>>M>>Q;
//     for(int i=1; i<N; i++) {
//         int u, v; cin>>u>>v;
//         adj[u].push_back(v), adj[v].push_back(u);
//     }
//     DFS(1, 0);
//     for(int i=1; i<20; i++) for(int j=1; j<=N; j++) P[i][j]=P[i-1][P[i-1][j]];
//     for(int i=1; i<=M; i++) cin>>C[i];
//     TL.Init();
//     DFS2(1, 0);
//     return 0;
// }

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010, S=(1<<17);
int N, M, Q, C[Nmax];

class Seg {
public:
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    int Query(int l, int r) {
        pair<int, int> tmp=Query(1, 1, S, l, r);
        return tmp.first-tmp.second;
    }
private:
    int Mn[2*S], Mx[2*S];
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            Mn[node]=Mx[node]=v;
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Mx[node]=max(Mx[lch], Mx[rch]), Mn[node]=min(Mn[lch], Mn[rch]);
    }
    pair<int, int> Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return {INT_MIN, INT_MAX};
        if(l<=s && e<=r) return {Mx[node], Mn[node]};
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        pair<int, int> a=Query(lch, s, m, l, r), b=Query(rch, m+1, e, l, r);
        return {max(a.first, b.first), min(a.second, b.second)};
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>Q;
    for(int i=1; i<N; i++) {
        int u, v; cin>>u>>v;
    }
    for(int i=1; i<=M; i++) cin>>C[i], T.Update(i, C[i]);
    while(Q--) {
        int l, r; cin>>l>>r;
        cout<<T.Query(l, r)+1<<"\n";
    }
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4440 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4440 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	45 ms	5536 KB	Output is correct
5	Correct	50 ms	5204 KB	Output is correct
6	Correct	66 ms	5456 KB	Output is correct
7	Correct	92 ms	5716 KB	Output is correct
8	Correct	87 ms	5724 KB	Output is correct
9	Correct	83 ms	5712 KB	Output is correct
10	Correct	72 ms	5716 KB	Output is correct
11	Correct	60 ms	5716 KB	Output is correct
12	Correct	54 ms	5904 KB	Output is correct
13	Correct	86 ms	5712 KB	Output is correct
14	Correct	54 ms	5712 KB	Output is correct
15	Correct	27 ms	4696 KB	Output is correct
16	Correct	60 ms	5456 KB	Output is correct
17	Correct	52 ms	5336 KB	Output is correct