oj.uz

Submission #282269

# Submission time Handle Problem Language Result Execution time Memory
282269 2020-08-24T08:27:57 Z 최은수(#5756) None (JOI15_walls) C++17
45 / 100
 962 ms 36472 KB 
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct fen
{
    pi t[mx];
    inline void upd(int x,pi p)
    {
        for(x=mx-3-x;x<mx;x+=x&-x)
            t[x]=max(t[x],p);
        return;
    }
    inline pi query(int x)
    {
        pi ret(-3,0);
        for(x=mx-3-x;x>0;x^=x&-x)
            ret=max(ret,t[x]);
        return ret;
    }
}fl,fr;
ll cans;
int ccnt;
inline void upd(pi x,pi y,int typ)
{
    cans+=typ*abs(x.fi-y.fi);
    if(x.se!=y.se)
        ccnt+=typ;
    return;
}
map<int,pi>mp;
inline void put(pair<pi,int>q)
{
    int tm=q.fi.fi;
    int pos=q.fi.se;
    int typ=q.se;
    auto it=mp.lower_bound(tm);
    if(it!=mp.begin())
    {
        auto it2=it;
        it2--;
        if(it!=mp.end())
            upd(it->se,it2->se,-1);
        upd(pi(pos,typ),it2->se,1);
    }
    if(it!=mp.end())
        upd(pi(pos,typ),it->se,1);
    mp[tm]=pi(pos,typ);
    return;
}
int a[mx],b[mx];
ll ans[mx];
vector<pair<pi,int> >mv[mx];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i],b[i]-=a[i];
    vector<int>v(n);
    for(int i=0;i<n;i++)
        v[i]=i;
    sort(all(v),[&](const int&x,const int&y){return b[x]<b[y];});
    int pp=0;
    for(int i=0;i<n;i++)
        fl.upd(i,pi(-1,0)),fr.upd(i,pi(-2,0));
    for(int i=0;i<m;i++)
    {
        int p;
        cin>>p;
        int s=-1,e=n-1;
        while(s<e)
        {
            int md=s+(e-s+1)/2;
            pi p1=fl.query(md);
            pi p2=fr.query(md);
            p2.se-=b[v[md]];
            int cp=max(p1,p2).se;
            if(p<cp||p>cp+b[v[md]])
                s=md;
            else
                e=md-1;
        }
        if(s>=0)
        {
            if(pp<p)
                fr.upd(s,pi(i,p));
            else
                fl.upd(s,pi(i,p));
            mv[s].eb(pi(i,p),pp<p?1:0);
            pp=p;
        }
    }
    mp[-1]=pi(0,0);
    for(int i=n;i-->0;)
    {
        for(auto&t:mv[i])
            put(t);
        ans[v[i]]=cans-(ll)b[v[i]]*ccnt;
    }
    for(int i=0;i<n;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7672 KB Output is correct
2 Correct 520 ms 24312 KB Output is correct
3 Correct 166 ms 19204 KB Output is correct
4 Correct 862 ms 36168 KB Output is correct
5 Correct 910 ms 36088 KB Output is correct
6 Correct 904 ms 36472 KB Output is correct
7 Correct 962 ms 36088 KB Output is correct
8 Correct 846 ms 36216 KB Output is correct
9 Correct 235 ms 17220 KB Output is correct
10 Correct 378 ms 35192 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5824 KB Output isn't correct
2 Halted 0 ms 0 KB -