oj.uz

Submission #289802

# Submission time Handle Problem Language Result Execution time Memory
289802 2020-09-03T05:14:52 Z 문홍윤(#5788) None (JOI12_invitation) C++17
40 / 100
 1363 ms 90088 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;
}

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

int main(){
    scanf("%d %d %d", &n, &m, &st);
    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);
    for(int i=1; i<n+m-2; i++){
        pii nxt=get_nxt();
        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();
            sega.update(1, 1, n-1, nxt.S);
        }
        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();
            segb.update(1, 1, m-1, nxt.S);
        }
    }
    printf("%lld", ans);
}

Compilation message

invitation.cpp: In function 'int main()':
invitation.cpp:177:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |     scanf("%d %d %d", &n, &m, &st);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
invitation.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  179 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
invitation.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  181 |         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 26 ms 38008 KB Output is correct
2 Correct 27 ms 38016 KB Output is correct
3 Correct 28 ms 38016 KB Output is correct
4 Correct 28 ms 38016 KB Output is correct

Subtask #2
0.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 38400 KB Output is correct
2 Correct 29 ms 38144 KB Output is correct

Subtask #4
0.0 / 10.0

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

Subtask #5
0.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 87040 KB Output is correct
2 Correct 251 ms 43872 KB Output is correct

Subtask #7
0.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1297 ms 87008 KB Output is correct
2 Correct 249 ms 43876 KB Output is correct
3 Correct 668 ms 64608 KB Output is correct

Subtask #9
0.0 / 10.0

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

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 44132 KB Output is correct
2 Correct 1136 ms 80612 KB Output is correct
3 Incorrect 1207 ms 85220 KB Output isn't correct