oj.uz

Submission #969748

# Submission time Handle Problem Language Result Execution time Memory
969748 2024-04-25T14:19:02 Z Warinchai Holiday (IOI14_holiday) C++14
47 / 100
 5000 ms 7160 KB 
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
long long rvid[100005];
struct segtree{
    long long info[400005];
    long long freq[400005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        //cerr<<"range:"<<st<<" "<<en<<"\n";
        if(st==en)return info[i]+=val,freq[i]++,void();
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
        freq[i]=freq[i*2]+freq[i*2+1];
    }
    void un_upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return info[i]-=val,freq[i]-=1,void();
        int m=(st+en)/2;
        un_upd(st,m,i*2,pos,val);
        un_upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
        freq[i]=freq[i*2]+freq[i*2+1];
    }
    long long fans(int st,int en,int i,long long pos){
        //cerr<<"Range:"<<st<<" "<<en<<"\n";
        if(st==en)return min(freq[i],pos)*(rvid[st]);
        int m=(st+en)/2;
        if(pos<=freq[i*2+1])return fans(m+1,en,i*2+1,pos);
        else return fans(st,m,i*2,pos-freq[i*2+1])+info[i*2+1];
    }
}tr;
vector<long long>v;
int id[100005];
map<int,int>mp;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(start!=0){
        for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++;
        sort(v.begin(),v.end());
        for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
        for(int i=0;i<n;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1;
        long long ans=0;
        vector<int>tinf;
        for(int i=0;i<n;i++){
            tinf.clear();
            assert(tr.info[1]==0);
            for(int j=i;j<n;j++){
                //tinf.push_back(attraction[j]);
                //sort(tinf.begin(),tinf.end(),greater<int>());
                ///int tsum=0;
                //int x=d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start));
                //int y=tinf.size();
                //for(int k=0;k<min(x,y);k++)tsum+=tinf[k];
                //cerr<<i<<" "<<j<<"\n";
                tr.upd(1,n,1,id[j],attraction[j]);
                //cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n";
                //int temp=tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)));
                //if(tsum!=temp)cerr<<attraction[j]<<" "<<x<<" "<<i<<" "<<j<<" "<<tsum<<" "<<temp<<"\n";
                //assert(tsum==temp);
                if(start>=i&&start<=j&&min(abs(i-start),abs(j-start))*2+max(abs(i-start),abs(j-start))<=d)ans=max(ans,tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start))))/*,cerr<<tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)))<<"\n"*/;
                //cerr<<"max:"<<ans<<"\n";
            }
            //cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n";
            for(int j=i;j<n;j++){
                tr.un_upd(1,n,1,id[j],attraction[j]);
            }
        }
        return ans;
    }
    for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++;
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
    for(int i=0;i<n;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1;
    long long ans=0;
    vector<int>tinf;
    for(int i=0;i<n;i++){
        //tinf.push_back(attraction[j]);
        //sort(tinf.begin(),tinf.end(),greater<int>());
        ///int tsum=0;
        //int x=d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start));
        //int y=tinf.size();
        //for(int k=0;k<min(x,y);k++)tsum+=tinf[k];
        //cerr<<i<<" "<<j<<"\n";
        tr.upd(1,n,1,id[i],attraction[i]);
        //cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n";
        //int temp=tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)));
        //if(tsum!=temp)cerr<<attraction[j]<<" "<<x<<" "<<i<<" "<<j<<" "<<tsum<<" "<<temp<<"\n";
        //assert(tsum==temp);
        if(abs(i-start)<=d)ans=max(ans,tr.fans(1,n,1,d-abs(i-start)))/*,cerr<<tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)))<<"\n"*/;
        //cerr<<"max:"<<ans<<"\n";
    //cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n";
    }
    return ans;
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
      |                     ~^~~~~~~~~
holiday.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7004 KB Output is correct
2 Correct 17 ms 7000 KB Output is correct
3 Correct 22 ms 7004 KB Output is correct
4 Correct 23 ms 7160 KB Output is correct
5 Correct 24 ms 7004 KB Output is correct
6 Correct 8 ms 4956 KB Output is correct
7 Correct 14 ms 4952 KB Output is correct
8 Correct 16 ms 3100 KB Output is correct
9 Correct 6 ms 5028 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 3156 KB Output is correct
2 Correct 350 ms 4932 KB Output is correct
3 Correct 489 ms 5208 KB Output is correct
4 Correct 646 ms 5116 KB Output is correct
5 Correct 506 ms 2908 KB Output is correct
6 Correct 40 ms 2908 KB Output is correct
7 Correct 47 ms 4952 KB Output is correct
8 Correct 46 ms 4956 KB Output is correct
9 Correct 45 ms 2908 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5059 ms 6980 KB Time limit exceeded
2 Halted 0 ms 0 KB -