oj.uz

답안 #206118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206118 2020-03-02T09:59:43 Z alexandra_udristoiu 사다리꼴 (balkan11_trapezoid) C++14
65 / 100
 287 ms 15352 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[4 * 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
65.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 12 ms 632 KB Output is correct
7 Correct 14 ms 764 KB Output is correct
8 Correct 17 ms 888 KB Output is correct
9 Correct 29 ms 1528 KB Output is correct
10 Correct 56 ms 2808 KB Output is correct
11 Correct 70 ms 2936 KB Output is correct
12 Correct 148 ms 5744 KB Output is correct
13 Correct 173 ms 6372 KB Output is correct
14 Incorrect 201 ms 8568 KB Output isn't correct
15 Incorrect 215 ms 8568 KB Output isn't correct
16 Runtime error 233 ms 15352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 250 ms 9208 KB Output isn't correct
18 Incorrect 246 ms 9464 KB Output isn't correct
19 Incorrect 264 ms 9592 KB Output isn't correct
20 Incorrect 287 ms 9972 KB Output isn't correct