oj.uz

답안 #206119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206119 2020-03-02T10:00:37 Z alexandra_udristoiu 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 290 ms 8184 KB 
#include<iostream>
#include<algorithm>
#define DIM 100005
#define f first
#define s second
#define mod 30013
using namespace std;
int n, i, u, k, ind;
int w[2 * DIM], d[DIM], num[DIM];
pair<int, int> p[DIM], aint[8 * DIM], curr;
struct str{
    int a, b, c, d;
};
str v[DIM];
int cmp(str x, str y){
    return x.a < y.a;
}
int cautbin(int x){
    int st = 1, dr = k, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(w[mid] == x){
            return mid;
        }
        if(w[mid] < x){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
}
void update(int nod, int st, int dr, int p, int x, int y){
    if(st == dr){
        aint[nod] = make_pair(x, y);
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p, x, y);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p, x, y);
        }
        if(aint[2 * nod].f == aint[2 * nod + 1].f){
            aint[nod].f = aint[2 * nod].f;
            aint[nod].s = (aint[2 * nod].s + aint[2 * nod + 1].s) % mod;
        }
        else{
            if(aint[2 * nod].f > aint[2 * nod + 1].f){
                aint[nod] = aint[2 * nod];
            }
            else{
                aint[nod] = aint[2 * nod + 1];
            }
        }
    }
}
void query(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        if(curr.f < aint[nod].f){
            curr = aint[nod];
        }
        else{
            if(curr.f == aint[nod].f){
                curr.s = (curr.s + aint[nod].s) % mod;
            }
        }
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            query(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            query(2 * nod + 1, mid + 1, dr, p, u);
        }
    }
}
int main(){
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> v[i].a >> v[i].b >> v[i].c >> v[i].d;
        w[2 * i - 1] = v[i].c;
        w[2 * i] = v[i].d;
    }
    k = 2 * n;
    sort(w + 1, w + k + 1);
    for(i = 1; i <= n; i++){
        v[i].c = cautbin(v[i].c);
        v[i].d = cautbin(v[i].d);
    }
    sort(v + 1, v + n + 1, cmp);
    for(i = 1; i <= n; i++){
        p[i] = make_pair(v[i].b, i);
    }
    sort(p + 1, p + n + 1);
    u = 1;
    for(i = 1; i <= n; i++){
        while(u <= n && p[u].f < v[i].a){
            ind = p[u].s;
            u++;
            update(1, 1, k, v[ind].d, d[ind], num[ind]);
        }
        curr = make_pair(0, 0);
        query(1, 1, k, 1, v[i].c);
        if(curr.f == 0){
            d[i] = num[i] = 1;
        }
        else{
            d[i] = curr.f + 1;
            num[i] = curr.s;
        }
    }
    while(u <= n){
        ind = p[u].s;
        u++;
        update(1, 1, k, v[ind].d, d[ind], num[ind]);
    }
    cout<< aint[1].f <<" "<< aint[1].s;
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int cautbin(int)':
trapezoid.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 13 ms 632 KB Output is correct
7 Correct 15 ms 632 KB Output is correct
8 Correct 18 ms 760 KB Output is correct
9 Correct 29 ms 1272 KB Output is correct
10 Correct 56 ms 2168 KB Output is correct
11 Correct 71 ms 2296 KB Output is correct
12 Correct 142 ms 4472 KB Output is correct
13 Correct 170 ms 4856 KB Output is correct
14 Correct 201 ms 7032 KB Output is correct
15 Correct 213 ms 7416 KB Output is correct
16 Correct 234 ms 7544 KB Output is correct
17 Correct 252 ms 7800 KB Output is correct
18 Correct 241 ms 8056 KB Output is correct
19 Correct 266 ms 7544 KB Output is correct
20 Correct 290 ms 8184 KB Output is correct