oj.uz

Submission #639991

# Submission time Handle Problem Language Result Execution time Memory
639991 2022-09-13T06:21:23 Z azberjibiou Sweeping (JOI20_sweeping) C++17
100 / 100
 11139 ms 1307008 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 378720 KB Output is correct
2 Correct 230 ms 379116 KB Output is correct
3 Correct 193 ms 377696 KB Output is correct
4 Correct 190 ms 378604 KB Output is correct
5 Correct 196 ms 379580 KB Output is correct
6 Correct 181 ms 377836 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9197 ms 1219916 KB Output is correct
2 Correct 9340 ms 1219740 KB Output is correct
3 Correct 9406 ms 1219820 KB Output is correct
4 Correct 7451 ms 1218452 KB Output is correct
5 Correct 6681 ms 1219316 KB Output is correct
6 Correct 8000 ms 1206812 KB Output is correct
7 Correct 9123 ms 1219808 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10445 ms 1271728 KB Output is correct
2 Correct 10344 ms 1267976 KB Output is correct
3 Correct 8660 ms 1282904 KB Output is correct
4 Correct 8103 ms 1307008 KB Output is correct
5 Correct 9795 ms 1287572 KB Output is correct
6 Correct 10158 ms 1287372 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 10445 ms 1271728 KB Output is correct
2 Correct 10344 ms 1267976 KB Output is correct
3 Correct 8660 ms 1282904 KB Output is correct
4 Correct 8103 ms 1307008 KB Output is correct
5 Correct 9795 ms 1287572 KB Output is correct
6 Correct 10158 ms 1287372 KB Output is correct
7 Correct 10250 ms 1287788 KB Output is correct
8 Correct 11139 ms 1287608 KB Output is correct
9 Correct 10882 ms 1287760 KB Output is correct
10 Correct 8714 ms 1301936 KB Output is correct
11 Correct 8093 ms 1306656 KB Output is correct
12 Correct 10194 ms 1287072 KB Output is correct
13 Correct 10031 ms 1287212 KB Output is correct
14 Correct 2827 ms 748128 KB Output is correct
15 Correct 2280 ms 703108 KB Output is correct
16 Correct 10581 ms 1289460 KB Output is correct
17 Correct 9216 ms 1280436 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 378720 KB Output is correct
2 Correct 230 ms 379116 KB Output is correct
3 Correct 193 ms 377696 KB Output is correct
4 Correct 190 ms 378604 KB Output is correct
5 Correct 196 ms 379580 KB Output is correct
6 Correct 181 ms 377836 KB Output is correct
7 Correct 9197 ms 1219916 KB Output is correct
8 Correct 9340 ms 1219740 KB Output is correct
9 Correct 9406 ms 1219820 KB Output is correct
10 Correct 7451 ms 1218452 KB Output is correct
11 Correct 6681 ms 1219316 KB Output is correct
12 Correct 8000 ms 1206812 KB Output is correct
13 Correct 9123 ms 1219808 KB Output is correct
14 Correct 10445 ms 1271728 KB Output is correct
15 Correct 10344 ms 1267976 KB Output is correct
16 Correct 8660 ms 1282904 KB Output is correct
17 Correct 8103 ms 1307008 KB Output is correct
18 Correct 9795 ms 1287572 KB Output is correct
19 Correct 10158 ms 1287372 KB Output is correct
20 Correct 10250 ms 1287788 KB Output is correct
21 Correct 11139 ms 1287608 KB Output is correct
22 Correct 10882 ms 1287760 KB Output is correct
23 Correct 8714 ms 1301936 KB Output is correct
24 Correct 8093 ms 1306656 KB Output is correct
25 Correct 10194 ms 1287072 KB Output is correct
26 Correct 10031 ms 1287212 KB Output is correct
27 Correct 2827 ms 748128 KB Output is correct
28 Correct 2280 ms 703108 KB Output is correct
29 Correct 10581 ms 1289460 KB Output is correct
30 Correct 9216 ms 1280436 KB Output is correct
31 Correct 8492 ms 1155652 KB Output is correct
32 Correct 9469 ms 1179680 KB Output is correct
33 Correct 9697 ms 1179836 KB Output is correct
34 Correct 9395 ms 1181444 KB Output is correct
35 Correct 9459 ms 1181760 KB Output is correct
36 Correct 8245 ms 1189884 KB Output is correct
37 Correct 7607 ms 1194908 KB Output is correct
38 Correct 9142 ms 1180068 KB Output is correct
39 Correct 9523 ms 1178708 KB Output is correct
40 Correct 9941 ms 1178784 KB Output is correct