Submission #206119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
206119	2020-03-02T10:00:37 Z	alexandra_udristoiu	trapezoid (balkan11_trapezoid)	C++14	100 / 100	290 ms	8184 KB

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[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

#	Verdict	Execution time	Memory	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