Submission #231138

#	Time	Username	Problem	Language	Result	Execution time	Memory
231138		summitwei	trapezoid (balkan11_trapezoid)	C++17	95 / 100	520 ms	29688 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define INF 0x3f3f3f3f
#define MOD 30013
#define f first
#define s second
#define pb push_back

#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define F0R(i, a) for(int i=0; i<a; ++i)

#define MN 100005
int n;
pair<pii, pii> a[MN];

pii tree[MN*8];
pii merge(pii a, pii b){
    if(a.f != b.f) return max(a, b);
    else return {a.f, (a.s+b.s)%MOD};
}
void upd(int node, int a, int b, int i, pii val){
    if(a > i || b < i) return;
    if(a == b){
        tree[node] = val;
        return;
    }
    int mid = (a+b)/2;
    upd(node*2, a, mid, i, val);
    upd(node*2+1, mid+1, b, i, val);
    tree[node] = merge(tree[node*2], tree[node*2+1]);
}
pii que(int node, int a, int b, int i, int j){
    if(a > j || b < i) return {0, 0};
    if(i <= a && b <= j) return tree[node];

    int mid = (a+b)/2;
    pii q1 = que(node*2, a, mid, i, j);
    pii q2 = que(node*2+1, mid+1, b, i, j);
    return merge(q1, q2);
}
pii bruh[MN*2]; //index, change

map<int, int> top, bot;
pii dp[MN];
int main(){
    cin >> n;
    F0R(i, n){
        cin >> a[i].f.f >> a[i].f.s >> a[i].s.f >> a[i].s.s;
        top[a[i].f.f] = top[a[i].f.s] = bot[a[i].s.f] = bot[a[i].s.s] = 0;
    }
    int t = 0;
    for(auto &u : top) u.s = ++t;
    t = 0;
    for(auto &u : bot) u.s = ++t;
    F0R(i, n){
        a[i].f.f = top[a[i].f.f];
        a[i].f.s = top[a[i].f.s];
        a[i].s.f = bot[a[i].s.f];
        a[i].s.s = bot[a[i].s.s];
        bruh[a[i].f.f] = {i, 0};
        bruh[a[i].f.s] = {i, 1};
        //cout << a[i].f.f << " " << a[i].f.s << " " << a[i].s.f << " " << a[i].s.s << "\n";
    }
    FOR(i, 1, 2*n){
        int j = bruh[i].f;
        if(bruh[i].s){
            //include
            upd(1, 1, 2*n, a[j].s.s, dp[j]);
            //cout << "upd " << j+1 << " " << a[j].s.s << " " << dp[j].f << " " << dp[j].s << "\n";
        } else{
            //cout << "que " << a[j].s.f << "\n";
            pii res = que(1, 1, 2*n, 1, a[j].s.f);
            res.f++;
            if(res.s == 0) res.s=1;
            dp[j] = res;
            //cout << j+1 << " has " << res.f << " " << res.s << "\n";
        }
    }
    pii ans = {0, 0};
    F0R(i, n){
        ans = merge(ans, dp[i]);
    }
    cout << ans.f << " " << ans.s << "\n";
}

• Subtask 1: 95 / 100