Submission #639991

#	Time	Username	Problem	Language	Result	Execution time	Memory
639991		azberjibiou	Sweeping (JOI20_sweeping)	C++17	100 / 100	11139 ms	1307008 KiB

sweeping

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=500005;
const int mxQ=1000010;
const int mxM=3000010;
const ll MOD=1000000007;
const ll INF=1e18;
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, -1, -1, -1, 0, 1, 1, 1};
typedef struct qry{
    int idx, typ, a, b;
}qry;
typedef struct cmp1{
    bool operator()(pii a, pii b){
        return a.fi!=b.fi ? a.fi<b.fi : a.se>b.se;
    }
}cmp1;
int N, M, Q;
pii A[mxN+mxQ];
int tim[mxN+mxQ];
qry B[mxQ];
vector <pii> ct[4*mxQ], seg[4*mxQ];
vector <pair<pii, int>> sct[4*mxQ];
vector <int> st[4*mxQ];
void input()
{
    cin >> N >> M >> Q;
    for(int i=1;i<=M;i++)   cin >> A[i].fi >> A[i].se;
    int dc=M;
    for(int i=1;i<=Q;i++)
    {
        B[i].idx=i;
        cin >> B[i].typ;
        if(B[i].typ==4) cin >> B[i].a >> B[i].b;
        else    cin >> B[i].a;
        if(B[i].typ==2 || B[i].typ==3)
        {
            B[i].a++;
            if(B[i].a>N)    B[i].typ=5;
        }
        if(B[i].typ==2) B[i].a=N-B[i].a;
        if(B[i].typ==4) tim[++dc]=i, A[dc]=pii(B[i].a, B[i].b);
    }
}
pii ts[4*mxN];
void init(int idx, int s, int e, pii val)
{
    ts[idx]=val;
    if(s==e)    return;
    int mid=(s+e)/2;
    init(2*idx, s, mid, val);
    init(2*idx+1, mid+1, e, val);
}
void tupd(int idx, int s1, int e1, int s2, int e2, pii val)
{
    if(s2<=s1 && e1<=e2)
    {
        if(ts[idx].se-ts[idx].fi>val.se-val.fi) ts[idx]=val;
        return;
    }
    if(s2>e1 || s1>e2)  return;
    int mid=(s1+e1)/2;
    tupd(2*idx, s1, mid, s2, e2, val);
    tupd(2*idx+1, mid+1, e1, s2, e2, val);
}
pii tsolv(int idx, int s1, int e1, int pos)
{
    if(s1==e1)  return ts[idx];
    int mid=(s1+e1)/2;
    pii ret;
    if(pos<=mid)    ret=tsolv(2*idx, s1, mid, pos);
    else    ret=tsolv(2*idx+1, mid+1, e1, pos);
    return (ret.se-ret.fi<ts[idx].se-ts[idx].fi) ? ret : ts[idx];
}
void dfs(int idx, int pos, vector<pii> &v, vector<pii> &lr)
{
    if(lr[pos].fi!=0)   dfs(idx, lr[pos].fi, v, lr);
    ct[idx].push_back(v[pos]);
    if(lr[pos].fi==0)   st[idx].push_back(v[pos].fi);
    else    st[idx].push_back(v[lr[pos].fi].se+1);
    if(lr[pos].se!=0)   dfs(idx, lr[pos].se, v, lr);
}
void seg_init(int ii, int idx, int s, int e)
{
    if(s==e)
    {
        seg[ii][idx]=ct[ii][s];
        return;
    }
    int mid=(s+e)/2;
    seg_init(ii, 2*idx, s, mid);
    seg_init(ii, 2*idx+1, mid+1, e);
    seg[ii][idx]=((seg[ii][2*idx].se-seg[ii][2*idx].fi>seg[ii][2*idx+1].se-seg[ii][2*idx+1].fi) ? seg[ii][2*idx] : seg[ii][2*idx+1]);
}
void make_seg(int idx, int s, int e)
{
    //printf("idx=%d, s=%d, e=%d\n", idx, s, e);
    vector <pii> v, lr;
    vector <int> cr;
    for(int i=s;i<=e;i++)   if(B[i].typ==2 || B[i].typ==3)  cr.push_back(B[i].a);
    cr.push_back(0), cr.push_back(N);
    sort(cr.begin(), cr.end());
    cr.erase(unique(cr.begin(), cr.end()), cr.end());
    //printf("cr: ");
    //for(int ele : cr)   printf("%d ", ele);
    //printf("\n");
    int K=cr.size();
    init(1, 0, K-1, pii(0, K-1));
    v.emplace_back(0, K-1);
    for(int i=s;i<=e;i++)
    {
        if(B[i].typ!=2 && B[i].typ!=3)  continue;
        int np=lower_bound(cr.begin(), cr.end(), B[i].a)-cr.begin();
        //printf("np=%d\n", np);
        pii rng=tsolv(1, 0, K-1, np), now;
        //printf("rng=%d, %d\n", rng.fi, rng.se);
        if(B[i].typ==2)
        {
            if(rng.se==np)  continue;
            if(cr[np+1]==cr[np]+1 && tsolv(1, 0, K-1, np+1)!=rng)   continue;
        }
        if(B[i].typ==3)
        {
            if(rng.fi==np)  continue;
            if(cr[np-1]==cr[np]-1 && tsolv(1, 0, K-1, np-1)!=rng)   continue;
        }
        if(B[i].typ==2) now=pii(rng.fi, np);
        if(B[i].typ==3) now=pii(np, rng.se);
        //printf("rng=%d, %d\n", rng.fi, rng.se);
        tupd(1, 0, K-1, now.fi, now.se, now);
        v.push_back(now);
    }
    for(pii &ele : v)   ele.fi=cr[ele.fi], ele.se=cr[ele.se];
    sort(v.begin(), v.end(), cmp1());
    //for(pii ele : v)    printf("(%d, %d) ", ele.fi, ele.se);
    //printf("\n");
    lr.resize(v.size());
    stack <pair<pii, int>> stk;
    for(int i=0;i<v.size();i++)
    {
        while(stk.size() && stk.top().fi.se<v[i].fi)  stk.pop();
        if(stk.size())
        {
            if(stk.top().fi.fi==v[i].fi) lr[stk.top().se].fi=i;
            else    lr[stk.top().se].se=i;
        }
        stk.emplace(v[i], i);
    }
    //for(int i=0;i<lr.size();i++)    printf("(%d, %d) ", lr[i].fi, lr[i].se);
    //printf("\n");

    dfs(idx, 0, v, lr);

    //for(int i=0;i<ct[idx].size();i++)   printf("(%d, %d) ", ct[idx][i].fi, ct[idx][i].se);
    //printf("\n");
    //for(int i=0;i<st[idx].size();i++)   printf("%d ", st[idx][i]);
    //printf("\n");
    seg[idx].resize(4*ct[idx].size());
    seg_init(idx, 1, 0, v.size()-1);
    sct[idx].resize(ct[idx].size());
    for(int i=0;i<ct[idx].size();i++)
    {
        sct[idx][i].fi=ct[idx][i];
        sct[idx][i].se=i;
    }
    sort(sct[idx].begin(), sct[idx].end());
    if(s==e)    return;
    int mid=(s+e)/2;
    make_seg(2*idx, s, mid);
    make_seg(2*idx+1 ,mid+1, e);
}
pii seg_solv(int ii, int idx, int s1, int e1, int s2, int e2)
{
    if(s1>e2 || s2>e1)  return pii(1, 0);
    if(s2<=s1 && e1<=e2)    return seg[ii][idx];
    int mid=(s1+e1)/2;
    pii ret1=seg_solv(ii, 2*idx, s1, mid, s2, e2), ret2=seg_solv(ii, 2*idx+1, mid+1, e1, s2, e2);
    if(ret1.se-ret1.fi<ret2.se-ret2.fi) return ret2;
    else    return ret1;
}
pii f(int idx, pii xy)
{
    //printf("idx=%d, xy=%d, %d\n", idx, xy.fi, xy.se);
    int l=upper_bound(st[idx].begin(), st[idx].end(), xy.fi)-st[idx].begin()-1;
    int r=upper_bound(st[idx].begin(), st[idx].end(), N-xy.se)-st[idx].begin()-1;
    pii rng=seg_solv(idx, 1, 0, ct[idx].size()-1, l, r);
    //printf("rng=%d, %d\n", rng.fi, rng.se);
    int pos=lower_bound(sct[idx].begin(), sct[idx].end(), pair<pii, int>(rng, -1))-sct[idx].begin();
    pos=sct[idx][pos].se;
    //printf("pos=%d\n", pos);
    if(pos!=0 && ct[idx][pos].fi<=ct[idx][pos-1].fi && ct[idx][pos-1].se<=ct[idx][pos].se)  rng.fi=ct[idx][pos-1].se+1;
    if(pos!=ct[idx].size()-1 && ct[idx][pos].fi<=ct[idx][pos+1].fi && ct[idx][pos+1].se<=ct[idx][pos].se)    rng.se=ct[idx][pos+1].fi-1;
    //printf("rng=%d, %d\n", rng.fi, rng.se);
    xy.fi=max(xy.fi, rng.fi);
    xy.se=max(xy.se, N-rng.se);
    return xy;
}
pii solv(int idx, int s1, int e1, int s2, int e2, pii xy)
{
    if(s2>e1 || s1>e2)  return xy;
    if(s2<=s1 && e1<=e2)    return f(idx, xy);
    int mid=(s1+e1)/2;
    pii xy1=solv(2*idx, s1, mid, s2, e2, xy);
    return solv(2*idx+1, mid+1, e1, s2, e2, xy1);
}
int main()
{
    gibon
    input();
    make_seg(1, 1, Q);
    for(int i=1;i<=Q;i++)   if(B[i].typ==1)
    {
        pii ret=solv(1, 1, Q, tim[B[i].a], i, A[B[i].a]);
        //printf("i=%d\n", i);
        cout << ret.fi << " " << ret.se << '\n';
    }
}

Compilation message (stderr)

sweeping.cpp: In function 'void make_seg(int, int, int)':
sweeping.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
sweeping.cpp:171:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for(int i=0;i<ct[idx].size();i++)
      |                 ~^~~~~~~~~~~~~~~
sweeping.cpp: In function 'std::pair<int, int> f(int, std::pair<int, int>)':
sweeping.cpp:202:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     if(pos!=ct[idx].size()-1 && ct[idx][pos].fi<=ct[idx][pos+1].fi && ct[idx][pos+1].se<=ct[idx][pos].se)    rng.se=ct[idx][pos+1].fi-1;
      |        ~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25