Submission #1306081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306081		Zbyszek99	수확 (JOI20_harvest)	C++20	5 / 100	5096 ms	83112 KiB

harvest

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long long,long long>, null_type, less<pair<long long,long long>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct dp
{
    ordered_set points;
    ll offset = 0;
    void insert(pll x)
    {
        points.insert({x.ff-offset,x.ss});
    }
    void move(ll x)
    {
        offset += x;
    }
    ll get_ans(ll t)
    {
        if(siz(points) == 0) return 0;
        auto it = points.upper_bound({t-offset,1e9});
        if(it == points.end()) return siz(points);
        return points.order_of_key(*it);
    }
    void merge(dp& other)
    {
        if(siz(other.points) > siz(points))
        {
            swap(other.points,points);
            swap(offset,other.offset);
        }
        forall(it,other.points) insert({it.ff+other.offset,it.ss});
    }
};

int n,m;
ll L,C;
int A[200001];
int B[200001];
vector<pll> queries[200001];
ll query_ans[200001];
vector<pll> graph[200001];
pll nxt[200001];
set<pii> A_set;
bool odw[200001];
bool is_cycle[200001];
dp points[200001];
vector<vi> cycles;

vi st;

void dfs_cycles(int v)
{
    st.pb(v);
    odw[v] = 1;
    if(!odw[nxt[v].ff])
    {
        dfs_cycles(nxt[v].ff);
        st.pop_back();
        return;
    }
    vi cycle;
    bool was = 0;
    while(siz(st) > 0)
    {
        cycle.pb(st.back());
        if(st.back() == nxt[v].ff)
        {
            was = 1;
            st.pop_back();
            break;
        }
        st.pop_back();
    }
    reverse(all(cycle));
    forall(it,cycle) st.pb(it);
    if(was) cycles.pb(cycle);
    st.pop_back();
}

void dfs_tree(int v)
{
    forall(it,graph[v])
    {
        if(is_cycle[it.ff]) continue;
        dfs_tree(it.ff);
        points[it.ff].move(it.ss);
        points[v].merge(points[it.ff]);
    }
    if(!is_cycle[v]) forall(it,queries[v]) query_ans[it.ss] = points[v].get_ans(it.ff);
}

void solve(vi c)
{
    forall(it,c) is_cycle[it] = 1;
    forall(it,c) dfs_tree(it);
    ll cycle_siz = 0;
    forall(it,c) cycle_siz += nxt[it].ss;
    ll cur_time = nxt[c[0]].ss;
    rep2(i,1,siz(c)-1)
    {
        forall(it,queries[c[i]])
        {
            query_ans[it.ss] = points[c[i]].get_ans(it.ff);
            queries[c[0]].pb({it.ff-cur_time,it.ss});
        }
        cur_time += nxt[c[i]].ss;
        points[c[i]].move(nxt[c[i]].ss);
        points[c[(i+1)%siz(c)]].merge(points[c[i]]);
    }
    vector<pll> p;
    forall(it,points[c[0]].points) p.pb({it.ff+points[c[0]].offset,it.ss});
    int cur_p = 0;
    ordered_set pom;
    sort(all(queries[c[0]]));
    ll del = 0;
    ll cnt = 0;
    forall(it,queries[c[0]])
    {
        while(cur_p < siz(p) && p[cur_p].ff <= it.ff)
        {
            cnt++;
            del += (p[cur_p].ff-1)/cycle_siz;
            pom.insert({p[cur_p].ff%cycle_siz,p[cur_p].ss});
            cur_p++;
        }
        ll mod_add = 0;
        auto it2 = pom.upper_bound({it.ff%cycle_siz,1e9});
        if(it2 == pom.end()) mod_add = cnt;
        else mod_add = pom.order_of_key(*it2);
        query_ans[it.ss] += cnt*(it.ff/cycle_siz)-del+mod_add;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n >> m >> L >> C;
    rep(i,n) cin >> A[i];
    rep(i,m) cin >> B[i];
    int q;
    cin >> q;
    rep(qq,q)
    {
        int v;
        ll t;
        cin >> v >> t;
        queries[v-1].pb({t,qq});
    }
    rep(i,n) A_set.insert({A[i],i});
    rep(i,n)
    {
        int ind = (A[i]-C+(ll)1e9*L)%L;
        auto it = A_set.upper_bound({ind,1e9});
        if(it != A_set.begin()) it--;
        else it = --A_set.end();
        nxt[i] = {(*it).ss,C+(ind-(*it).ff+L)%L};
    }
    rep(i,m)
    {
        auto it = A_set.upper_bound({B[i],1e9});
        if(it != A_set.begin()) it--;
        else it = --A_set.end();
        points[(*it).ss].insert({(B[i]-(*it).ff+L)%L,i});
    }
    rep(i,n) graph[nxt[i].ff].pb({i,nxt[i].ss});
    rep(i,n) if(!odw[i]) dfs_cycles(i);
    forall(it,cycles) solve(it);
    rep(qq,q) cout << query_ans[qq] << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75