Submission #257340

# Submission time Handle Problem Language Result Execution time Memory
257340 2020-08-04T06:29:20 Z 문홍윤(#5062) None (JOI16_worst_reporter2) C++17
0 / 100
3 ms 4992 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())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
const int inf=1e8;

struct LAZY_SEGMENT_TREE{
    int x;
    struct NODE{
        int st, fin;
        int minn, lazy;
    }tree[1600000];
    void init(int point, int num){
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        init(point*2, num-num/2);
        init(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void eat(int point){
        tree[point].minn=min(tree[point*2].minn+tree[point*2].lazy, tree[point*2+1].minn+tree[point*2+1].lazy);
    }
    void propogate(int point){
        if(tree[point].st==tree[point].fin){
            tree[point].minn+=tree[point].lazy;
            tree[point].lazy=0;
            return;
        }
        tree[point].minn+=tree[point].lazy;
        tree[point*2].lazy+=tree[point].lazy;
        tree[point*2+1].lazy+=tree[point].lazy;
        tree[point].lazy=0;
    }
    void alter(int point, int a, int b, LL qu){
        if(tree[point].st>=a&&tree[point].fin<=b){
            tree[point].lazy+=qu;
            return;
        }
        if(tree[point].st>b||tree[point].fin<a)return;
        propogate(point);
        alter(point*2, a, b, qu);
        alter(point*2+1, a, b, qu);
        eat(point);
    }
    int query(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].minn+tree[point].lazy;
        if(tree[point].st>b||tree[point].fin<a)return inf;
        propogate(point);
        int ret=min(query(point*2, a, b), query(point*2+1, a, b));
        eat(point);
        return ret;
    }
    void init(int num){init(1, num);}
    void alter(int a, int b, int qu){alter(1, a, b, qu);}
    int query(int a, int b){return query(1, a, b);}
}seg;

int n, ans;
int arra[200010], xa[200010];
int arrb[200010], xb[200010];
vector<int> id, stk[200010];

int main(){
    seg.init(2*n);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arra[i], &xa[i]);
        id.eb(xa[i]);
    }
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arrb[i], &xb[i]);
        id.eb(xb[i]);
    }
    reverse(arra+1, arra+n+1);
    reverse(arrb+1, arrb+n+1);
    reverse(xa+1, xa+n+1);
    reverse(xb+1, xb+n+1);
    svec(id); press(id);
    for(int i=1; i<=n; i++){
        xa[i]=lb(id, xa[i])-id.begin()+1;
        xb[i]=lb(id, xb[i])-id.begin()+1;
        seg.alter(xa[i], xb[i]-1, 1);
    }
    int pv=1;
    ans=n;
    for(int i=1; i<=n; i++){
        for(; pv<=n; pv++){
            if(xa[pv]>xb[i])break;
            stk[arra[pv]].eb(xa[pv]);
        }
        if(stk[arrb[i]].size()==0)continue;
        if(seg.query(stk[arrb[i]].back(), xb[i]-1)>=1){
            seg.alter(stk[arrb[i]].back(), xb[i]-1, -1);
            stk[arrb[i]].pop_back();
            ans--;
        }
    }
    printf("%d", ans);
}


/*
6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10
*/

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &arra[i], &xa[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &arrb[i], &xb[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -