Submission #1089732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089732		phong	Harvest (JOI20_harvest)	C++17	25 / 100	2061 ms	524288 KiB

harvest

#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 (stderr)

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 75