oj.uz

답안 #739414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739414 2023-05-10T12:25:08 Z josanneo22 사다리꼴 (balkan11_trapezoid) C++17
100 / 100
 182 ms 16072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
 
const int mod = 30013;
 
int n;
int a[100005], b[100005], c[100005], d[100005];
int dp[100005], cnt[100005];
 
struct seg{int a,b,p,i;}st[200005];
bool cmp(seg a, seg b){return make_tuple(a.a, a.b, a.p) < make_tuple(b.a, b.b, b.p); }
struct seg2{int dp,a,b,p,i;}st2[200005];
bool cmp2(seg2 a, seg2 b){return make_tuple(a.a, a.b, a.p) < make_tuple(b.a, b.b, b.p); }
 
struct rmq{
    int lim, tree[530000];
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void ins(int s, int v){
        s += lim;
        tree[s] = max(tree[s], v);
        while(s>1){
            s >>= 1;
            tree[s] = max(tree[2*s],tree[2*s+1]);
        }
    }
    int q(int s, int e){
        s += lim;
        e += lim;
        int r = 0;
        while(s<e){
            if(s%2 == 1) r = max(r,tree[s++]);
            if(e%2 == 0) r = max(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = max(r,tree[s]);
        return r;
    }
}rmq;
 
struct bit{
    int lim, tree[132000];
    void init(int n){
        n += 2;
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, int v){
        x += 2;
        while(x <= lim){
            tree[x] += v;
            tree[x] %= mod;
            x += x & -x;
        }
    }
    int sum(int x){
        x += 2;
        int r = 0;
        while(x){
            r += tree[x];
            r %= mod;
            x -= x & -x;
        }
        return r;
    }
}idx;
 
void input(){
    vector<int> vu, vd;
    scanf("%d",&n);
    rmq.init(2*n);
    for (int i=0; i<n; i++) {
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
        vu.push_back(a[i]);
        vu.push_back(b[i]);
        vd.push_back(c[i]);
        vd.push_back(d[i]);
    }
    sort(vu.begin(),vu.end());
    sort(vd.begin(),vd.end());
    for (int i=0; i<n; i++) {
        a[i] = (int)(lower_bound(vu.begin(),vu.end(),a[i]) - vu.begin());
        b[i] = (int)(lower_bound(vu.begin(),vu.end(),b[i]) - vu.begin());
        c[i] = (int)(lower_bound(vd.begin(),vd.end(),c[i]) - vd.begin());
        d[i] = (int)(lower_bound(vd.begin(),vd.end(),d[i]) - vd.begin());
        st[2*i] = {a[i],c[i],0,i};
        st[2*i+1] = {b[i],d[i],1,i};
    }
    sort(st,st+2*n,cmp);
}
 
vector<pi> v;
 
int main(){
    input();
    for (int i=0; i<2*n; i++) {
        if(st[i].p == 0){
            dp[st[i].i] = rmq.q(0,st[i].b) + 1;
            st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i};
        }
        else{
            rmq.ins(st[i].b,dp[st[i].i]);
            st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i};
        }
    }
    int mcnt = *max_element(dp,dp+n);
    printf("%d ",mcnt);
    for (int i=0; i<2*n; i++) {
        if(st2[i].p == 1) v.push_back(pi(st2[i].dp,st2[i].b));
    }
    sort(v.begin(),v.end());
    sort(st2,st2+2*n,cmp2);
    idx.init(n);
    int acnt = 0;
    for (int i=0; i<2*n; i++) {
        if(st2[i].p == 0){
            if(st2[i].dp == 1){
                cnt[st2[i].i] = 1;
            }
            else{
                int start = (int)(lower_bound(v.begin(),v.end(),pi(st2[i].dp-1,0)) - v.begin());
                int end = (int)(lower_bound(v.begin(),v.end(),pi(st2[i].dp-1,st2[i].b)) - v.begin());
                cnt[st2[i].i] = idx.sum(end-1) - idx.sum(start-1);
                if(st2[i].dp == mcnt) acnt += cnt[st2[i].i];
            }
        }
        else{
            int pos = (int)(lower_bound(v.begin(),v.end(),pi(st2[i].dp,st2[i].b)) - v.begin());
            idx.add(pos,cnt[st2[i].i]);
        }
        acnt %= mod;
    }
    if(acnt < 0) acnt += mod;
    printf("%d",acnt);
}

Compilation message

trapezoid.cpp: In function 'void input()':
trapezoid.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
trapezoid.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 5 ms 836 KB Output is correct
7 Correct 6 ms 932 KB Output is correct
8 Correct 8 ms 1176 KB Output is correct
9 Correct 18 ms 1948 KB Output is correct
10 Correct 34 ms 3576 KB Output is correct
11 Correct 41 ms 4332 KB Output is correct
12 Correct 94 ms 8216 KB Output is correct
13 Correct 108 ms 9728 KB Output is correct
14 Correct 139 ms 11860 KB Output is correct
15 Correct 147 ms 12380 KB Output is correct
16 Correct 155 ms 13324 KB Output is correct
17 Correct 164 ms 13908 KB Output is correct
18 Correct 157 ms 14632 KB Output is correct
19 Correct 166 ms 15392 KB Output is correct
20 Correct 182 ms 16072 KB Output is correct