Submission #206118

#	Time	Username	Problem	Language	Result	Execution time	Memory
206118		alexandra_udristoiu	trapezoid (balkan11_trapezoid)	C++14	65 / 100	287 ms	15352 KiB

trapezoid

#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 (stderr)

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

• Subtask 1: 65 / 100