oj.uz

답안 #945863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945863 2024-03-14T08:15:25 Z guagua0407 수확 (JOI20_harvest) C++17
5 / 100
 191 ms 62664 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct BIT{
    vector<int> bit;
    int n;
    BIT(int N){
        n=N;
        bit=vector<int>(n,0);
    }
    void update(int pos,int val){
        for(;pos<n;pos+=(pos&-pos)){
            bit[pos]+=val;
        }
    }
    int query(int pos){
        int ans=0;
        for(;pos>0;pos-=(pos&-pos)){
            ans+=bit[pos];
        }
        return ans;
    }
};

const int mxn=200000+5;
const int inf=1e18;
int a[mxn];
int b[mxn];
int nxt[mxn*2];
bool visited[mxn*2];
bool is_cycle[mxn*2];
vector<pair<int,ll>> adj[mxn*2];
int belong[mxn*2];
ll depth[mxn*2];
ll d[mxn*2];
ll sum[mxn*2];
int rev[mxn*2];
int st[mxn*2],en[mxn*2];
vector<pair<int,int>> sta;
vector<pair<int,int>> js[mxn];
vector<pair<pair<int,int>,int>> is[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
int timer=0;

void dfs(int id,int p,int v){
    st[v]=++timer;
    if(v>=n){
        sta.push_back({depth[v]-pre[id][rev[p]],p});
        //cout<<"dfs "<<depth[v]-pre[0][rev[p]]<<'\n';
    }
    for(auto u:adj[v]){
        if(is_cycle[u.f]) continue;
        depth[u.f]=depth[v]+u.s;
        dfs(id,p,u.f);
    }
    en[v]=timer;
}

signed main() {_
    cin>>n>>m>>l>>c;
    ll C=c;
    c%=l;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        if(a[i]-c>=a[0]){
            nxt[i]=upper_bound(a,a+n,a[i]-c)-a-1;
            d[i]=a[i]-a[nxt[i]];
        }
        else{
            int val=(a[i]-c+l);
            nxt[i]=upper_bound(a,a+n,val)-a-1;
            d[i]=a[i]+l-a[nxt[i]];
        }
        if(d[i]==0){
            d[i]=(C+l-1)/l*l;
        }
        else{
            d[i]+=1ll*(C/l)*l;
        }
    }
    for(int i=0;i<m;i++){
        if(b[i]>=a[0]){
            nxt[i+n]=upper_bound(a,a+n,b[i])-a-1;
            d[i+n]=b[i]-a[nxt[i+n]];
        }
        else{
            int val=(b[i]+l);
            nxt[i+n]=upper_bound(a,a+n,val)-a-1;
            d[i+n]=b[i]+l-a[nxt[i+n]];
        }
    }
    for(int i=0;i<n+m;i++){
        adj[nxt[i]].push_back({i,d[i]});
    }
    vector<vector<int>> cycle;
    for(int i=0;i<n+m;i++){
        if(visited[i]) continue;
        int x=i;
        vector<int> tmp;
        while(!visited[x]){
            visited[x]=true;
            tmp.push_back(x);
            x=nxt[x];
        }
        bool ok=false;
        for(auto v:tmp){
            ok|=(v==x);
            is_cycle[v]=ok;
        }
        if(!ok) continue;
        vector<int> curcycle;
        for(auto v:tmp){
            if(is_cycle[v]){
                curcycle.push_back(v);
                belong[v]=(int)cycle.size();
            }
        }
        cycle.push_back(curcycle);
        vector<ll> dis;
        dis.push_back(0);
        for(int i=1;i<(int)curcycle.size();i++){
            dis.push_back(dis.back()+d[curcycle[i-1]]);
        }
        for(int i=0;i<(int)curcycle.size();i++){
            int prv=(i-1+(int)curcycle.size())%(int)curcycle.size();
            dis.push_back(dis.back()+d[curcycle[prv]]);
        }
        pre.push_back(dis);
        for(int i=0;i<(int)curcycle.size();i++){
            rev[curcycle[i]]=i;
        }
    }
    for(int i=0;i<(int)cycle.size();i++){
        int cnt=0;
        for(auto v:cycle[i]){
            sta.clear();
            dfs(i,v,v);
            js[i].insert(js[i].end(),all(sta));
            sum[i]+=d[v];
            //rev[v]=cnt++;
        }
    }
    int q;
    cin>>q;
    vector<pair<ll,pair<int,int>>> qys;
    vector<int> res(q);
    for(int i=0;i<q;i++){
        int v;
        ll t;
        cin>>v>>t;
        v--;
        if(!is_cycle[v]){
            qys.push_back({t+depth[v],{i,v}});
            continue;
        }
        int id=belong[v];
        is[id].push_back({{t-pre[id][rev[v]],v},i});
    }
    // tree
    {
        for(int i=n;i<n+m;i++){
            qys.push_back({depth[i],{-1,i}});
        }
        sort(qys.begin(),qys.end());
        BIT T(mxn);
        for(auto query:qys){
            int id=query.s.f;
            int v=query.s.s;
            if(id==-1){
                T.update(st[v],1);
            }
            else{
                res[id]=T.query(en[v])-T.query(st[v]-1);
            }
        }
    }
    // cycle
    for(int t=0;t<(int)cycle.size();t++){
        //continue;
        {
            vector<pair<pair<int,int>,int>> vec;
            vector<int> xs;
            xs.push_back(-inf);
            for(auto v:is[t]){
                int a=v.f.f/sum[t];
                assert(sum[t]!=0);
                if(a*sum[t]>v.f.f) a--;
                int b=v.f.f-a*sum[t];
                //cout<<"sir "<<v.f.f<<' '<<rev[v.f.s]<<' '<<a<<' '<<b<<'\n';
                xs.push_back(b);
                vec.push_back({{a,v.s},b});
            }
            //cout<<'\n';
            for(auto v:js[t]){
                int a=v.f/sum[t];
                assert(sum[t]!=0);
                if(a*sum[t]>v.f) a--;
                int b=v.f-a*sum[t];
                //cout<<"sir "<<v.f<<' '<<rev[v.s]<<' '<<a<<' '<<b<<'\n';
                xs.push_back(b);
                vec.push_back({{a,-1},b});
            }
            sort(all(xs));
            xs.resize(unique(all(xs))-xs.begin());
            sort(all(vec));
            int sum2=0;
            int cnt=0;
            BIT T(xs.size());
            for(auto v:vec){
                int pos=lower_bound(all(xs),v.s)-xs.begin();
                if(v.f.s==-1){
                    sum2+=v.f.f;
                    //cout<<"sir "<<v.f.f<<'\n';
                    cnt++;
                    T.update(pos,1);
                }
                else{
                    int i=v.f.s;
                    res[i]+=cnt*v.f.f;
                    res[i]-=sum2;
                    res[i]+=T.query(pos);
                }
            }
        }
        //continue;
        {
            vector<pair<pair<int,int>,int>> vec;
            vector<int> xs;
            xs.push_back(-inf);
            for(auto v:is[t]){
                xs.push_back(v.f.f);
                vec.push_back({{rev[v.f.s],v.s},v.f.f});
            }
            for(auto v:js[t]){
                xs.push_back(v.f);
                vec.push_back({{rev[v.s],-1},v.f});
            }
            sort(all(xs));
            xs.resize(unique(all(xs))-xs.begin());
            sort(all(vec));
            reverse(all(vec));
            BIT T(xs.size());
            //continue;-
            for(auto v:vec){
                int pos=lower_bound(all(xs),v.s)-xs.begin();
                //cout<<pos<<'\n';
                //continue;
                if(v.f.s==-1){
                    T.update(pos,1);
                }
                else{
                    int i=v.f.s;
                    //cout<<"sir "<<T.query(pos)<<'\n';
                    res[i]-=T.query(pos);
                }
            }
        }
    }
    for(int i=0;i<q;i++){
        cout<<res[i]<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
/*
1 1 2 5
0
1
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
*/

Compilation message

harvest.cpp: In function 'int main()':
harvest.cpp:156:13: warning: unused variable 'cnt' [-Wunused-variable]
  156 |         int cnt=0;
      |             ^~~
harvest.cpp: In function 'void setIO(std::string)':
harvest.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 39304 KB Output is correct
2 Correct 14 ms 40028 KB Output is correct
3 Correct 12 ms 39804 KB Output is correct
4 Correct 11 ms 39732 KB Output is correct
5 Correct 12 ms 39976 KB Output is correct
6 Correct 11 ms 39976 KB Output is correct
7 Correct 11 ms 39972 KB Output is correct
8 Correct 12 ms 39720 KB Output is correct
9 Correct 10 ms 39720 KB Output is correct
10 Correct 11 ms 39548 KB Output is correct
11 Correct 11 ms 39716 KB Output is correct
12 Correct 11 ms 39772 KB Output is correct
13 Correct 12 ms 39772 KB Output is correct
14 Correct 12 ms 39772 KB Output is correct
15 Correct 11 ms 39796 KB Output is correct
16 Correct 11 ms 39720 KB Output is correct
17 Correct 12 ms 39776 KB Output is correct
18 Correct 11 ms 39720 KB Output is correct
19 Correct 12 ms 39720 KB Output is correct
20 Correct 10 ms 39720 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 57284 KB Output is correct
2 Incorrect 149 ms 62664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 39304 KB Output is correct
2 Correct 14 ms 40028 KB Output is correct
3 Correct 12 ms 39804 KB Output is correct
4 Correct 11 ms 39732 KB Output is correct
5 Correct 12 ms 39976 KB Output is correct
6 Correct 11 ms 39976 KB Output is correct
7 Correct 11 ms 39972 KB Output is correct
8 Correct 12 ms 39720 KB Output is correct
9 Correct 10 ms 39720 KB Output is correct
10 Correct 11 ms 39548 KB Output is correct
11 Correct 11 ms 39716 KB Output is correct
12 Correct 11 ms 39772 KB Output is correct
13 Correct 12 ms 39772 KB Output is correct
14 Correct 12 ms 39772 KB Output is correct
15 Correct 11 ms 39796 KB Output is correct
16 Correct 11 ms 39720 KB Output is correct
17 Correct 12 ms 39776 KB Output is correct
18 Correct 11 ms 39720 KB Output is correct
19 Correct 12 ms 39720 KB Output is correct
20 Correct 10 ms 39720 KB Output is correct
21 Correct 191 ms 57284 KB Output is correct
22 Incorrect 149 ms 62664 KB Output isn't correct
23 Halted 0 ms 0 KB -