oj.uz

Submission #1089505

# Submission time Handle Problem Language Result Execution time Memory
1089505 2024-09-16T15:33:50 Z phong Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 226512 KB 
#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 5e5 + 5, N = 1e6;
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;
//                cout << u << ' ' << v << ' ' << mp[v][u] << endl;

        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{

}str;

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);
        }
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());

    for(int i = 1; i <= one.size(); ++i){
        int u = one[i - 1];
        for(auto [id, T] : Q[u]){
//            cout << id << ' ';
            for(int p = 1; p < i; ++p){
                for(auto j : hos[p]){
//                    cout << dis[j] + dos[u] << ' ' << j << ' ' << u << endl;
                    if(T - dos[u] >= dis[j]){
                        ans[id] += (T - dos[u] - dis[j]) / len;
                        ans[id]++;
                    }
                }
            }
            for(int p = i; p <= one.size(); ++p){
                for(auto j : hos[p]){
//                    cout << u << ' ' << j <<' '<< T << ' ' << dis[u] - dis[j] << endl;
                    if(T + dis[u] >= dis[j]){
                        ans[id] += (T + dis[u] - dis[j]) / len;
                        ans[id]++;
                    }
                }
            }
        }
    }
//    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:86:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     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:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     int mid = r + l >> 1;
      |               ~~^~~
harvest.cpp: In function 'void solve(long long int)':
harvest.cpp:165: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]
  165 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:181: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]
  181 |     for(int i = 1; i <= one.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
harvest.cpp:194:30: 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]
  194 |             for(int p = i; p <= one.size(); ++p){
      |                            ~~^~~~~~~~~~~~~
harvest.cpp: At global scope:
harvest.cpp:210:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  210 | main(){
      | ^~~~
harvest.cpp: In function 'int main()':
harvest.cpp:228:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  228 |             int mid = r + l >> 1;
      |                       ~~^~~
harvest.cpp:253:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  253 |             int mid = r+ l >> 1;
      |                       ~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 129944 KB Output is correct
2 Correct 61 ms 131304 KB Output is correct
3 Correct 79 ms 131796 KB Output is correct
4 Correct 59 ms 131916 KB Output is correct
5 Correct 60 ms 132288 KB Output is correct
6 Correct 58 ms 132172 KB Output is correct
7 Correct 60 ms 132180 KB Output is correct
8 Correct 73 ms 131920 KB Output is correct
9 Correct 61 ms 131924 KB Output is correct
10 Correct 60 ms 131920 KB Output is correct
11 Correct 63 ms 131924 KB Output is correct
12 Correct 83 ms 132384 KB Output is correct
13 Correct 84 ms 132432 KB Output is correct
14 Correct 72 ms 131880 KB Output is correct
15 Correct 64 ms 131920 KB Output is correct
16 Correct 76 ms 132180 KB Output is correct
17 Correct 65 ms 131920 KB Output is correct
18 Correct 65 ms 132028 KB Output is correct
19 Correct 60 ms 131924 KB Output is correct
20 Correct 60 ms 131920 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 147136 KB Output is correct
2 Correct 361 ms 200680 KB Output is correct
3 Correct 229 ms 191568 KB Output is correct
4 Correct 1589 ms 194240 KB Output is correct
5 Correct 280 ms 221108 KB Output is correct
6 Correct 272 ms 221120 KB Output is correct
7 Correct 213 ms 196836 KB Output is correct
8 Correct 220 ms 196892 KB Output is correct
9 Execution timed out 5033 ms 226512 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 129944 KB Output is correct
2 Correct 61 ms 131304 KB Output is correct
3 Correct 79 ms 131796 KB Output is correct
4 Correct 59 ms 131916 KB Output is correct
5 Correct 60 ms 132288 KB Output is correct
6 Correct 58 ms 132172 KB Output is correct
7 Correct 60 ms 132180 KB Output is correct
8 Correct 73 ms 131920 KB Output is correct
9 Correct 61 ms 131924 KB Output is correct
10 Correct 60 ms 131920 KB Output is correct
11 Correct 63 ms 131924 KB Output is correct
12 Correct 83 ms 132384 KB Output is correct
13 Correct 84 ms 132432 KB Output is correct
14 Correct 72 ms 131880 KB Output is correct
15 Correct 64 ms 131920 KB Output is correct
16 Correct 76 ms 132180 KB Output is correct
17 Correct 65 ms 131920 KB Output is correct
18 Correct 65 ms 132028 KB Output is correct
19 Correct 60 ms 131924 KB Output is correct
20 Correct 60 ms 131920 KB Output is correct
21 Correct 1641 ms 147136 KB Output is correct
22 Correct 361 ms 200680 KB Output is correct
23 Correct 229 ms 191568 KB Output is correct
24 Correct 1589 ms 194240 KB Output is correct
25 Correct 280 ms 221108 KB Output is correct
26 Correct 272 ms 221120 KB Output is correct
27 Correct 213 ms 196836 KB Output is correct
28 Correct 220 ms 196892 KB Output is correct
29 Execution timed out 5033 ms 226512 KB Time limit exceeded
30 Halted 0 ms 0 KB -