oj.uz

답안 #1089735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089735 2024-09-17T04:57:46 Z phong 수확 (JOI20_harvest) C++17
25 / 100
 2035 ms 524288 KB 
#include<bits/stdc++.h>
#define ll long long
//#define int long long
const int nmax = 4e5 + 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;

ll n, m, L, C;
pii a[nmax], b[nmax];
pii c[nmax];
vector<pii> inp[nmax], out[nmax], adj[nmax];
map<int, ll>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];
ll 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<ll> tree[1 << 20];
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, ll 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];
ll 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{
    ll f[M + 5];
    vector<int> tmp;
    void clear(){
        for(auto p : tmp) f[p] = 0;
        tmp.clear();
    }
    void update(int u, ll val){
        for(; u <= M; u += u &-u) f[u] += val, tmp.push_back(u);
    }
    ll get(int u){
        ll 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;

vector<ll> one, nen;

int calc( ll 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;
    one.clear();
    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;
        for(auto [id, T] : Q[u]){
            int l = st[u], r = en[u];
            ans[id] = get(1, 1, Time, l, r, T + dis[u]);
        }
    }

    for(auto p : tmp) vis[p] = 0;
    dfs_4(root);//xây dos vòng tròn
    nen.clear();
    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( T - dos[u]);
            int y = calc((T - dos[u]) % len);
            con.Fake_get(x, y);
        }
        for(auto j : hos[i]){
            int x = calc(dis[j]);
            int y = calc(dis[j] % len);
            con.Fake_update(x, y);
        }
    }
    for(int i = 1; i <= one.size(); ++i){
        int u = one[i - 1];
        for(auto [id, T] : Q[u]){
            int x = calc(T - dos[u]);
            int y = calc((T - dos[u]) % len);
            ans[id] += ((T - dos[u]) / len) * str[0].get(x);
            ans[id] += str[0].get(x);
            ans[id] -= str[1].get(x);
            ans[id] -= con.get(x, y);
        }
        for(auto j : hos[i]){
            int x = calc(dis[j]);
            int y = calc( dis[j] % len);
            str[0].update(x, 1);
            str[1].update(x, dis[j] / len);
            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(T + dis[u]);
            int y = calc((T + dis[u]) % len);
            con.Fake_get(x, y);
        }
        for(auto j : hos[i]){
            int x = calc( dis[j]);
            int y = calc(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( dis[j]);
            int y = calc( 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(T + dis[u]);
            int y = calc((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;
        ll 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 = 1ll * 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){
            ll 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;
            ll 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(int, int, int)':
harvest.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = r + l >> 1;
      |               ~~^~~
harvest.cpp: In function 'int get(int, int, int, int, 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 'int cay3::get(int, int)':
harvest.cpp:173:97: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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(int)':
harvest.cpp:223:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:243:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:256:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:275:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp: At global scope:
harvest.cpp:315:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  315 | main(){
      | ^~~~
harvest.cpp: In function 'int main()':
harvest.cpp:334:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  334 |             int mid = r + l >> 1;
      |                       ~~^~~
harvest.cpp:359:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  359 |             int mid = r+ l >> 1;
      |                       ~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 232528 KB Output is correct
2 Correct 118 ms 233304 KB Output is correct
3 Correct 120 ms 235872 KB Output is correct
4 Correct 116 ms 235468 KB Output is correct
5 Correct 111 ms 235724 KB Output is correct
6 Correct 108 ms 235724 KB Output is correct
7 Correct 115 ms 235724 KB Output is correct
8 Correct 106 ms 235532 KB Output is correct
9 Correct 112 ms 235464 KB Output is correct
10 Correct 110 ms 235360 KB Output is correct
11 Correct 117 ms 235308 KB Output is correct
12 Correct 116 ms 236408 KB Output is correct
13 Correct 122 ms 236728 KB Output is correct
14 Correct 116 ms 234960 KB Output is correct
15 Correct 106 ms 235464 KB Output is correct
16 Correct 107 ms 235628 KB Output is correct
17 Correct 104 ms 235604 KB Output is correct
18 Correct 101 ms 235572 KB Output is correct
19 Correct 104 ms 235540 KB Output is correct
20 Correct 111 ms 235740 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1200 ms 290128 KB Output is correct
2 Correct 353 ms 300992 KB Output is correct
3 Correct 285 ms 292324 KB Output is correct
4 Correct 1316 ms 337004 KB Output is correct
5 Correct 319 ms 320964 KB Output is correct
6 Correct 304 ms 320876 KB Output is correct
7 Correct 262 ms 295548 KB Output is correct
8 Correct 257 ms 295696 KB Output is correct
9 Correct 1667 ms 380320 KB Output is correct
10 Correct 1594 ms 374440 KB Output is correct
11 Correct 1863 ms 382856 KB Output is correct
12 Correct 1760 ms 382928 KB Output is correct
13 Correct 1854 ms 382660 KB Output is correct
14 Correct 1608 ms 377268 KB Output is correct
15 Correct 1317 ms 339312 KB Output is correct
16 Correct 308 ms 309980 KB Output is correct
17 Correct 277 ms 309508 KB Output is correct
18 Correct 196 ms 264004 KB Output is correct
19 Correct 190 ms 264004 KB Output is correct
20 Correct 333 ms 301512 KB Output is correct

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 232528 KB Output is correct
2 Correct 118 ms 233304 KB Output is correct
3 Correct 120 ms 235872 KB Output is correct
4 Correct 116 ms 235468 KB Output is correct
5 Correct 111 ms 235724 KB Output is correct
6 Correct 108 ms 235724 KB Output is correct
7 Correct 115 ms 235724 KB Output is correct
8 Correct 106 ms 235532 KB Output is correct
9 Correct 112 ms 235464 KB Output is correct
10 Correct 110 ms 235360 KB Output is correct
11 Correct 117 ms 235308 KB Output is correct
12 Correct 116 ms 236408 KB Output is correct
13 Correct 122 ms 236728 KB Output is correct
14 Correct 116 ms 234960 KB Output is correct
15 Correct 106 ms 235464 KB Output is correct
16 Correct 107 ms 235628 KB Output is correct
17 Correct 104 ms 235604 KB Output is correct
18 Correct 101 ms 235572 KB Output is correct
19 Correct 104 ms 235540 KB Output is correct
20 Correct 111 ms 235740 KB Output is correct
21 Correct 1200 ms 290128 KB Output is correct
22 Correct 353 ms 300992 KB Output is correct
23 Correct 285 ms 292324 KB Output is correct
24 Correct 1316 ms 337004 KB Output is correct
25 Correct 319 ms 320964 KB Output is correct
26 Correct 304 ms 320876 KB Output is correct
27 Correct 262 ms 295548 KB Output is correct
28 Correct 257 ms 295696 KB Output is correct
29 Correct 1667 ms 380320 KB Output is correct
30 Correct 1594 ms 374440 KB Output is correct
31 Correct 1863 ms 382856 KB Output is correct
32 Correct 1760 ms 382928 KB Output is correct
33 Correct 1854 ms 382660 KB Output is correct
34 Correct 1608 ms 377268 KB Output is correct
35 Correct 1317 ms 339312 KB Output is correct
36 Correct 308 ms 309980 KB Output is correct
37 Correct 277 ms 309508 KB Output is correct
38 Correct 196 ms 264004 KB Output is correct
39 Correct 190 ms 264004 KB Output is correct
40 Correct 333 ms 301512 KB Output is correct
41 Correct 1338 ms 482484 KB Output is correct
42 Correct 727 ms 332520 KB Output is correct
43 Correct 1118 ms 329432 KB Output is correct
44 Correct 2035 ms 509572 KB Output is correct
45 Correct 1022 ms 493952 KB Output is correct
46 Correct 1118 ms 494660 KB Output is correct
47 Correct 1233 ms 496220 KB Output is correct
48 Correct 938 ms 493032 KB Output is correct
49 Correct 923 ms 495480 KB Output is correct
50 Correct 971 ms 476532 KB Output is correct
51 Correct 949 ms 472360 KB Output is correct
52 Runtime error 1240 ms 524288 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -