oj.uz

답안 #1089732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089732 2024-09-17T04:44:27 Z phong 수확 (JOI20_harvest) C++17
25 / 100
 2061 ms 524288 KB 
#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 5e5 + 5, M = 3e6 + 5;
const ll oo = 1e9 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7, mod2 = 1e9+3;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define NAME code
using namespace std;

int n, m, L, C;
pii a[nmax], b[nmax];
pii c[nmax];
vector<pii> inp[nmax], out[nmax], adj[nmax];
map<int, int>mp[nmax];
bool vis[nmax];
vector<int> tmp;
int root;

void dfs(int u, int p){
    vis[u] = 1;
    tmp.push_back(u);
    for(auto [w, v] : adj[u]){
        if(v == p) continue;
        if(vis[v]) root = v;
        else{
            vis[v] = 1;
            dfs(v, u);
        }
    }
}
/*
3 2 7 3
1 4 6
0 5
3
1 7
2 3
3 8
*/
int root_2, par[nmax];
ll dis[nmax];
int len = 0;
void dfs_2(int u){
    vis[u] = 1;
    for(auto [w, v] : out[u]){
//        cout << u << ' ' << v << ' ' << mp[v][u] << endl;
        if(vis[v]){
            root_2 = u;
            continue;
        }
        dis[v] = dis[u] + mp[v][u];
        par[v] = u;
        dfs_2(v);
    }
}

int tour[nmax], st[nmax], en[nmax], Time = 0;
void dfs_3(int u, int p){
    tour[++Time] = u;
    st[u] = Time;
    vis[u] = 1;
    for(auto [w, v]: out[u]){
        if(v == p || vis[v]) continue;
//        cerr<< u << ' ' << v << endl;
        dfs_3(v, u);
    }
    en[u] = Time;
}
ll ans[nmax];
vector<int> tree[nmax << 2];
void build(int id, int l, int r){
    tree[id].clear();
    if(l == r){
        int x = tour[l];
        if(x > n) tree[id].push_back(dis[x]);
        return;
    }
    int mid = r + l >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    tree[id].resize(tree[id << 1].size() + tree[id << 1 | 1].size());
    merge(tree[id << 1].begin(), tree[id << 1].end(), tree[id << 1 | 1].begin(), tree[id << 1 | 1].end(), tree[id].begin());
}

int get(int id, int l, int r, int u, int v, int k){
    if(tree[id].empty()) return 0;
    if(l >= u && r <= v){
        return upper_bound(tree[id].begin(), tree[id].end(), k) - tree[id].begin();
    }
    int mid = r + l >> 1;
    if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v, k);
    if(mid + 1 > v) return get(id << 1, l, mid, u, v, k);
    return get(id << 1, l, mid, u, v, k) +get(id << 1 | 1, mid + 1, r, u, v, k);
}

vector<pii> Q[nmax];
int dos[nmax];

void dfs_4(int u){
    vis[u] = 1;
    for(auto [w,v] : inp[u]){
        len += w;
        if(vis[v]) continue;
        dos[v] = dos[u] + w;
        dfs_4(v);
    }
}

vector<int> hos[nmax];

void dfs_5(int u, int p){
    if(u > n) hos[p].push_back(u);
    for(auto [w, v] : out[u]){
        if(vis[v]) continue;
        dfs_5(v,p);
    }
}
struct cay2{
    int f[M + 5];
    vector<int> tmp;
    void clear(){
        for(auto p : tmp) f[p] = 0;
        tmp.clear();
    }
    void update(int u, int val){
        for(; u <= M; u += u &-u) f[u] += val, tmp.push_back(u);
    }
    int get(int u){
        int res = 0;
        for(; u; u -= u&-u) res += f[u];
        return res;
    }

}str[2];

struct cay3{
    vector<int> tmp;
    vector<int> f[M + 5], note[M +5];
    void Fake_update(int x, int y){
        for(; x <= M; x += x&-x) note[x].push_back(y), tmp.push_back(x);
    }
    void Fake_get(int x, int y){
        for(; x; x -= x&-x) note[x].push_back(y), tmp.push_back(x);
    }
    void update(int x, int y, int val){
        for(; x <= M; x += x &-x){
            if(f[x].empty()){
                sort(note[x].begin(), note[x].end());
                note[x].erase(unique(note[x].begin(), note[x].end()), note[x].end());
                f[x].resize(note[x].size() + 2);
            }
            for(int j= lower_bound(note[x].begin(), note[x].end(), y) - note[x].begin() + 1; j ; j -= j&-j){
                f[x][j - 1] += val;
            }
            tmp.push_back(x);
        }
    }
    int get(int x, int y){
        ++y;
        int res = 0;
        for(; x; x -= x &-x){
            if(f[x].empty()){
                sort(note[x].begin(), note[x].end());
                note[x].erase(unique(note[x].begin(), note[x].end()), note[x].end());
                f[x].resize(note[x].size() + 2);
            }
            for(int j = lower_bound(note[x].begin(), note[x].end(), y) - note[x].begin() + 1; j <= note[x].size(); j += j&-j){
                res += f[x][j - 1];
            }
        }
        return res;
    }
    void clear(){
        for(auto p : tmp) f[p].clear(), note[p].clear();
        tmp.clear();
    }
}con;
int calc(vector<int> &nen, int val){
    return lower_bound(nen.begin(), nen.end(), val) - nen.begin() + 1;
}
void solve(int i){
    len = 0;
    tmp.clear();
    dfs(i, -1);//tìm tplt
    for(auto p : tmp) vis[p] = 0;
    dfs_2(root);//tạo dis()
    int x = root_2;
    vector<int> one;
    while(x != root){
        one.push_back(x);
        x = par[x];
    }
    one.push_back(root);
    reverse(one.begin(), one.end());
    //
    for(auto p : tmp) vis[p] = 0;
    Time = 0;
    dfs_3(root, -1);//xây euler tour
    for(auto p : tmp) vis[p] = 0;
    for(auto p : one) vis[p] = 1;
    build(1, 1, Time);
    for(auto u : tmp){
        if(vis[u]) continue;
//        cout << u <<"?" << endl;
        for(auto [id, T] : Q[u]){
//            cout << id << ' ';
            int l = st[u], r = en[u];
            ans[id] = get(1, 1, Time, l, r, T + dis[u]);
//            ans[id] = -1;
        }
    }

    for(auto p : tmp) vis[p] = 0;
    dfs_4(root);//xây dos vòng tròn
    vector<int> nen;
    for(int i = 1; i <= one.size(); ++i){
        int u = one[i - 1];
        hos[i].clear();
        dfs_5(u, i);
        for(auto j : hos[i]){
            nen.push_back(dis[j]);
            nen.push_back(dis[j] % len);
        }
        for(auto [id, T] : Q[u]){
            nen.push_back(T - dos[u]);
            nen.push_back((T - dos[u]) % len);
            nen.push_back(T + dis[u]);
            nen.push_back((T + dis[u]) % len);
        }
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
//    for(auto  p : tmp) vis[p] = 1;
//    for(auto p : tmp) cout << p << ' ';
//    cout << endl;
    for(int i = 1; i <= one.size(); ++i){
        int u = one[i - 1];
        for(auto [id, T] : Q[u]){
            int x = calc(nen, T - dos[u]);
            int y = calc(nen, (T - dos[u]) % len);
            con.Fake_get(x, y);
        }
        for(auto j : hos[i]){
            int x = calc(nen, dis[j]);
            int y = calc(nen, dis[j] % len);
            con.Fake_update(x, y);
        }
    }
    for(int i = 1; i <= one.size(); ++i){
        int u = one[i - 1];
//        cout << u << ' ';
        for(auto [id, T] : Q[u]){
            int x = calc(nen, T - dos[u]);
            int y = calc(nen, (T - dos[u]) % len);
            ans[id] += ((T - dos[u]) / len) * str[0].get(x);
            ans[id] += str[0].get(x);
//            cout << u << ' ' << T << ' ' << id<< endl;
            ans[id] -= str[1].get(x);
            ans[id] -= con.get(x, y);
        }
        for(auto j : hos[i]){
            int x = calc(nen, dis[j]);
            int y = calc(nen, dis[j] % len);
            str[0].update(x, 1);
            str[1].update(x, dis[j] / len);
//            cout << j << ' ' <<x << ' ';
            con.update(x, y, 1);
        }
    }
    str[0].clear();str[1].clear();con.clear();
    for(int i = 1; i <= one.size(); ++i){
        int u = one[i - 1];
        for(auto [id, T] : Q[u]){
            int x = calc(nen, T + dis[u]);
            int y = calc(nen, (T + dis[u]) % len);
            con.Fake_get(x, y);
        }
        for(auto j : hos[i]){
            int x = calc(nen, dis[j]);
            int y = calc(nen, dis[j] % len);
            con.Fake_update(x, y);
        }
    }
    for(int i = one.size(); i >= 1; --i){
        int u = one[i - 1];
        for(auto j : hos[i]){
            int x = calc(nen, dis[j]);
            int y = calc(nen, dis[j] % len);
            str[0].update(x, 1);
            str[1].update(x, dis[j] / len);
            con.update(x, y, 1);
//            cout << j << ' ' << dis[j] << endl;
        }
        for(auto [id, T] : Q[u]){
            int x = calc(nen, T + dis[u]);
            int y = calc(nen, (T + dis[u]) % len);
            ans[id] += ((T + dis[u]) / len) * (str[0].get(x));
            ans[id] += str[0].get(x);
//            cout << id << ' ' << T + dis[u] << ' ' << str[0].get(x) << endl;
            ans[id] -= str[1].get(x);
            ans[id] -= con.get(x, y);
        }
    }
       str[0].clear();str[1].clear();con.clear();

//    cout << len<<"#"<<endl;
    for(auto p : tmp) vis[p] = 1;


}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m >> L >> C;
    for(int i = 1; i <= n; ++i) cin >> a[i].fi, a[i].se = i;
    for(int i = 1; i <= m; ++i) cin >> b[i].fi, b[i].se = i + n;
    int q; cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> c[i].fi >> c[i].se;
        Q[c[i].fi].push_back({i, c[i].se});
    }
    for(int i = n + 1; i <= 2 * n; ++i){
        a[i] = a[i - n];
        int l = i - n + 1, r = i, kq = i, cur = L * (C / L) + L;
        int x = C % L;
        while(l <= r){
            int mid = r + l >> 1;
            int dist = 0;
            if(a[mid].fi > a[i].fi){
                dist = L - a[mid].fi + a[i].fi;
            }
            else dist = a[i].fi - a[mid].fi;
            if(dist >= x){
                l = mid + 1;
                kq = mid;
                cur = L * (C / L) + dist;
            }
            else r = mid - 1;
        }
        if(kq != -1){
//            cout << a[i].se << ' ' << a[kq].se << ' ' << cur  << endl;
            mp[a[i].se][a[kq].se] = cur;
            adj[a[i].se].push_back({cur, a[kq].se});
            adj[a[kq].se].push_back({cur, a[i].se});
            inp[a[i].se].push_back({cur, a[kq].se});
            out[a[kq].se].push_back({cur, a[i].se});
        }
    }
    for(int i = 1; i <= m; ++i){
        int l = 1, r = n, kq = -1;
        while(l <= r){
            int mid = r+ l >> 1;
            if(a[mid].fi <= b[i].fi){
                l = mid + 1;
                kq = mid;
            }
            else r = mid - 1;
        }
        if(kq != -1){
            int cur = b[i].fi - a[kq].fi;
            mp[b[i].se][a[kq].se] = cur;

            adj[b[i].se].push_back({cur, a[kq].se});
            adj[a[kq].se].push_back({cur, b[i].se});
            inp[b[i].se].push_back({cur, a[kq].se});
            out[a[kq].se].push_back({cur, b[i].se});
        }
        else{
            kq = n;
            int cur = b[i].fi + (L - a[kq].fi);
            mp[b[i].se][a[kq].se] = cur;
            adj[b[i].se].push_back({cur, a[kq].se});
            adj[a[kq].se].push_back({cur, b[i].se});
            inp[b[i].se].push_back({cur, a[kq].se});
            out[a[kq].se].push_back({cur, b[i].se});
        }
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            solve(i);
        }
    }

//    cout << dis[4]<< ' ' <<dis[3] << endl;
    for(int i = 1; i <= q; ++i) cout << ans[i] <<endl;
}
/*
5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237


8 15 217 33608
0 12 71 96 111 128 152 206
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212
14
2 223544052420046341
3 86357593875941375
4 892813012303440034
1 517156961659770735
7 415536186438473633
6 322175014520330760
7 557706040951533058
6 640041274241532527
5 286263974600593111
8 349405886653104871
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881
*/

Compilation message

harvest.cpp: In function 'void build(long long int, long long int, long long int)':
harvest.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = r + l >> 1;
      |               ~~^~~
harvest.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int, long long int)':
harvest.cpp:96:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |     int mid = r + l >> 1;
      |               ~~^~~
harvest.cpp: In member function 'long long int cay3::get(long long int, long long int)':
harvest.cpp:173:97: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |             for(int j = lower_bound(note[x].begin(), note[x].end(), y) - note[x].begin() + 1; j <= note[x].size(); j += j&-j){
      |                                                                                               ~~^~~~~~~~~~~~~~~~~
harvest.cpp: In function 'void solve(long long int)':
harvest.cpp:222:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:242:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:255:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:277:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  277 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp: At global scope:
harvest.cpp:317:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  317 | main(){
      | ^~~~
harvest.cpp: In function 'int main()':
harvest.cpp:335:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  335 |             int mid = r + l >> 1;
      |                       ~~^~~
harvest.cpp:360:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  360 |             int mid = r+ l >> 1;
      |                       ~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 271564 KB Output is correct
2 Correct 116 ms 272212 KB Output is correct
3 Correct 127 ms 276624 KB Output is correct
4 Correct 125 ms 275908 KB Output is correct
5 Correct 125 ms 276164 KB Output is correct
6 Correct 121 ms 276164 KB Output is correct
7 Correct 121 ms 276400 KB Output is correct
8 Correct 116 ms 276040 KB Output is correct
9 Correct 127 ms 276096 KB Output is correct
10 Correct 121 ms 275692 KB Output is correct
11 Correct 121 ms 275660 KB Output is correct
12 Correct 139 ms 276944 KB Output is correct
13 Correct 134 ms 277232 KB Output is correct
14 Correct 131 ms 274768 KB Output is correct
15 Correct 134 ms 275908 KB Output is correct
16 Correct 123 ms 275912 KB Output is correct
17 Correct 125 ms 275892 KB Output is correct
18 Correct 115 ms 276164 KB Output is correct
19 Correct 117 ms 276164 KB Output is correct
20 Correct 121 ms 275960 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1336 ms 347968 KB Output is correct
2 Correct 401 ms 345636 KB Output is correct
3 Correct 316 ms 332760 KB Output is correct
4 Correct 1490 ms 398192 KB Output is correct
5 Correct 328 ms 365248 KB Output is correct
6 Correct 336 ms 365268 KB Output is correct
7 Correct 285 ms 340248 KB Output is correct
8 Correct 305 ms 340172 KB Output is correct
9 Correct 1766 ms 443396 KB Output is correct
10 Correct 1644 ms 438476 KB Output is correct
11 Correct 2061 ms 451616 KB Output is correct
12 Correct 2005 ms 451492 KB Output is correct
13 Correct 1997 ms 450988 KB Output is correct
14 Correct 1805 ms 446428 KB Output is correct
15 Correct 1438 ms 393416 KB Output is correct
16 Correct 336 ms 353920 KB Output is correct
17 Correct 336 ms 353876 KB Output is correct
18 Correct 205 ms 305344 KB Output is correct
19 Correct 222 ms 305344 KB Output is correct
20 Correct 404 ms 345796 KB Output is correct

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 271564 KB Output is correct
2 Correct 116 ms 272212 KB Output is correct
3 Correct 127 ms 276624 KB Output is correct
4 Correct 125 ms 275908 KB Output is correct
5 Correct 125 ms 276164 KB Output is correct
6 Correct 121 ms 276164 KB Output is correct
7 Correct 121 ms 276400 KB Output is correct
8 Correct 116 ms 276040 KB Output is correct
9 Correct 127 ms 276096 KB Output is correct
10 Correct 121 ms 275692 KB Output is correct
11 Correct 121 ms 275660 KB Output is correct
12 Correct 139 ms 276944 KB Output is correct
13 Correct 134 ms 277232 KB Output is correct
14 Correct 131 ms 274768 KB Output is correct
15 Correct 134 ms 275908 KB Output is correct
16 Correct 123 ms 275912 KB Output is correct
17 Correct 125 ms 275892 KB Output is correct
18 Correct 115 ms 276164 KB Output is correct
19 Correct 117 ms 276164 KB Output is correct
20 Correct 121 ms 275960 KB Output is correct
21 Correct 1336 ms 347968 KB Output is correct
22 Correct 401 ms 345636 KB Output is correct
23 Correct 316 ms 332760 KB Output is correct
24 Correct 1490 ms 398192 KB Output is correct
25 Correct 328 ms 365248 KB Output is correct
26 Correct 336 ms 365268 KB Output is correct
27 Correct 285 ms 340248 KB Output is correct
28 Correct 305 ms 340172 KB Output is correct
29 Correct 1766 ms 443396 KB Output is correct
30 Correct 1644 ms 438476 KB Output is correct
31 Correct 2061 ms 451616 KB Output is correct
32 Correct 2005 ms 451492 KB Output is correct
33 Correct 1997 ms 450988 KB Output is correct
34 Correct 1805 ms 446428 KB Output is correct
35 Correct 1438 ms 393416 KB Output is correct
36 Correct 336 ms 353920 KB Output is correct
37 Correct 336 ms 353876 KB Output is correct
38 Correct 205 ms 305344 KB Output is correct
39 Correct 222 ms 305344 KB Output is correct
40 Correct 404 ms 345796 KB Output is correct
41 Runtime error 762 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -