oj.uz

Submission #289808

# Submission time Handle Problem Language Result Execution time Memory
289808 2020-09-03T05:32:37 Z 문홍윤(#5788) None (JOI12_invitation) C++17
100 / 100
 1469 ms 90588 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;

struct LAZY_SEG{
    LL tree[800010], lzy[800010];
    int num[800010];
    bool dead[800010];
    void prop(int point, int s, int e){
        if(s==e){
            if(!dead[point])tree[point]=max(tree[point], lzy[point]);
            lzy[point]=0;
            return;
        }
        lzy[point*2]=max(lzy[point*2], lzy[point]);
        lzy[point*2+1]=max(lzy[point*2+1], lzy[point]);
        lzy[point]=0;
    }
    void eat(int point, int s, int e){
        if(s==e)return;
        dead[point]=(dead[point*2]&&dead[point*2+1]);
        LL l=max(tree[point*2], lzy[point*2]);
        LL r=max(tree[point*2+1], lzy[point*2+1]);
        if(dead[point*2])l=0;
        if(dead[point*2+1])r=0;
        tree[point]=max(l, r);
        if(tree[point]==l)num[point]=num[point*2];
        else num[point]=num[point*2+1];
    }
    void alter(int point, int s, int e, int a, int b, LL val){
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            lzy[point]=max(lzy[point], val);
            return;
        }
        prop(point, s, e);
        alter(point*2, s, (s+e)/2, a, b, val);
        alter(point*2+1, (s+e)/2+1, e, a, b, val);
        eat(point, s, e);
    }
    void update(int point, int s, int e, int num){
        if(s==e){
            dead[point]=true;
            return;
        }
        prop(point, s, e);
        if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num);
        else update(point*2+1, (s+e)/2+1, e, num);
        eat(point, s, e);
    }
    pli query(){
        LL nw=max(tree[1], lzy[1]);
        if(dead[1])nw=0;
        return mp(nw, num[1]);
    }
    void init(int point, int s, int e){
        num[point]=s;
        if(s==e)return;
        init(point*2, s, (s+e)/2);
        init(point*2+1, (s+e)/2+1, e);
    }
}sega, segb;

int ch[100010];
struct UPD_SEG{
    vector<int> vc[800010];
    void update(int point, int s, int e, int a, int b, int val){
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            vc[point].eb(val);
            return;
        }
        update(point*2, s, (s+e)/2, a, b, val);
        update(point*2+1, (s+e)/2+1, e, a, b, val);
    }
    vector<int> query(int point, int s, int e, int num){
        vector<int> ret;
        if(s==e){
            for(auto i:vc[point]){
                if(ch[i])continue;
                ch[i]=true;
                ret.eb(i);
            }
            vc[point].clear();
            return ret;
        }
        if(num<=(s+e)/2)ret=query(point*2, s, (s+e)/2, num);
        else ret=query(point*2+1, (s+e)/2+1, e, num);
        for(auto i:vc[point]){
            if(ch[i])continue;
            ch[i]=true;
            ret.eb(i);
        }
        vc[point].clear();
        return ret;
    }
}cha, chb;

int n, m, st, q;
pair<pair<pii, pii>, LL> rng[100010];
vector<int> ida, idb;
int toa[200010], tob[200010];
LL ans;

void compress(){
    ida.eb(1); idb.eb(1);
    ida.eb(n); idb.eb(m);
    ida.eb(st); ida.eb(st+1);
    for(int i=1; i<=q; i++){
        ida.eb(rng[i].F.F.F);
        ida.eb(rng[i].F.F.S);
        idb.eb(rng[i].F.S.F);
        idb.eb(rng[i].F.S.S);
    }
    svec(ida); press(ida);
    svec(idb); press(idb);
    int tmp=lower_bound(all(ida), 1)-ida.begin()+1;
    toa[tmp]=1;
    tmp=lower_bound(all(ida), n)-ida.begin()+1;
    toa[tmp]=n;
    n=tmp;
    tmp=lower_bound(all(idb), 1)-idb.begin()+1;
    tob[tmp]=1;
    tmp=lower_bound(all(idb), m)-idb.begin()+1;
    tob[tmp]=m;
    m=tmp;
    for(int i=1; i<=q; i++){
        tmp=lower_bound(all(ida), rng[i].F.F.F)-ida.begin()+1;
        toa[tmp]=rng[i].F.F.F;
        rng[i].F.F.F=tmp;
        tmp=lower_bound(all(ida), rng[i].F.F.S)-ida.begin()+1;
        toa[tmp]=rng[i].F.F.S;
        rng[i].F.F.S=tmp;
        tmp=lower_bound(all(idb), rng[i].F.S.F)-idb.begin()+1;
        tob[tmp]=rng[i].F.S.F;
        rng[i].F.S.F=tmp;
        tmp=lower_bound(all(idb), rng[i].F.S.S)-idb.begin()+1;
        tob[tmp]=rng[i].F.S.S;
        rng[i].F.S.S=tmp;
    }
    tmp=lower_bound(all(ida), st+1)-ida.begin()+1;
    toa[tmp]=st+1;
    tmp=lower_bound(all(ida), st)-ida.begin()+1;
    toa[tmp]=st;
    st=tmp;
}

bool chka[200010], chkb[200010];
int cnta=1, cntb;

pii get_nxt(){
    pli a=sega.query();
    pli b=segb.query();
    if(a.F==0&&b.F==0)return mp(-1, 0);
    if(a.F<b.F){
        if(chkb[b.S])ans+=b.F*(LL)(tob[b.S+1]-tob[b.S]-1), cntb+=tob[b.S+1]-tob[b.S]-1;
        else ans+=b.F, cntb++;
        return mp(2, b.S);
    }
    if(chka[a.S])ans+=a.F*(LL)(toa[a.S+1]-toa[a.S]-1), cnta+=toa[a.S+1]-toa[a.S]-1;
    else ans+=a.F, cnta++;
    return mp(1, a.S);
}

int rn, rm;

int main(){
    scanf("%d %d %d", &n, &m, &st);
    rn=n, rm=m;
    n++, m++;
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d %d %d %lld", &rng[i].F.F.F, &rng[i].F.F.S, &rng[i].F.S.F, &rng[i].F.S.S, &rng[i].S);
        rng[i].F.F.S++;
        rng[i].F.S.S++;
    }
    compress();
    for(int i=1; i<=q; i++){
        cha.update(1, 1, n-1, rng[i].F.F.F, rng[i].F.F.S-1, i);
        chb.update(1, 1, m-1, rng[i].F.S.F, rng[i].F.S.S-1, i);
    }
    sega.init(1, 1, n-1);
    segb.init(1, 1, m-1);
    vector<int> del=cha.query(1, 1, n-1, st);
    for(auto i:del){
        sega.alter(1, 1, n-1, rng[i].F.F.F, rng[i].F.F.S-1, rng[i].S);
        segb.alter(1, 1, m-1, rng[i].F.S.F, rng[i].F.S.S-1, rng[i].S);
    }
    del.clear();
    sega.update(1, 1, n-1, st);
    chka[st]=true;
    while(1){
        pii nxt=get_nxt();
        if(nxt.F==-1)break;
        if(nxt.F==1){
            del=cha.query(1, 1, n-1, nxt.S);
            for(auto i:del){
                sega.alter(1, 1, n-1, rng[i].F.F.F, rng[i].F.F.S-1, rng[i].S);
                segb.alter(1, 1, m-1, rng[i].F.S.F, rng[i].F.S.S-1, rng[i].S);
            }
            del.clear();
            if(chka[nxt.S]||toa[nxt.S+1]-toa[nxt.S]==1)sega.update(1, 1, n-1, nxt.S);
            chka[nxt.S]=true;
        }
        else{
            del=chb.query(1, 1, m-1, nxt.S);
            for(auto i:del){
                sega.alter(1, 1, n-1, rng[i].F.F.F, rng[i].F.F.S-1, rng[i].S);
                segb.alter(1, 1, m-1, rng[i].F.S.F, rng[i].F.S.S-1, rng[i].S);
            }
            del.clear();
            if(chkb[nxt.S]||tob[nxt.S+1]-tob[nxt.S]==1)segb.update(1, 1, m-1, nxt.S);
            chkb[nxt.S]=true;
        }
    }
    if(cnta!=rn||cntb!=rm)printf("-1");
    else printf("%lld", ans);
}

Compilation message

invitation.cpp: In function 'int main()':
invitation.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  181 |     scanf("%d %d %d", &n, &m, &st);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
invitation.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  184 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
invitation.cpp:186:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  186 |         scanf("%d %d %d %d %lld", &rng[i].F.F.F, &rng[i].F.F.S, &rng[i].F.S.F, &rng[i].F.S.S, &rng[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 38008 KB Output is correct
2 Correct 26 ms 38016 KB Output is correct
3 Correct 26 ms 38016 KB Output is correct
4 Correct 26 ms 38016 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 38008 KB Output is correct
2 Correct 27 ms 38016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 38392 KB Output is correct
2 Correct 28 ms 38144 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 38816 KB Output is correct
2 Correct 38 ms 38784 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 38784 KB Output is correct
2 Correct 37 ms 38776 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1391 ms 87168 KB Output is correct
2 Correct 251 ms 44000 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 90588 KB Output is correct
2 Correct 904 ms 87320 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1397 ms 87256 KB Output is correct
2 Correct 243 ms 43880 KB Output is correct
3 Correct 683 ms 64868 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1301 ms 85820 KB Output is correct
2 Correct 887 ms 87296 KB Output is correct
3 Correct 614 ms 63076 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 44132 KB Output is correct
2 Correct 1190 ms 80864 KB Output is correct
3 Correct 1326 ms 85732 KB Output is correct