Submission #231139

#	Time	Username	Problem	Language	Result	Execution time	Memory
231139		summitwei	trapezoid (balkan11_trapezoid)	C++17	100 / 100	464 ms	24568 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*2];
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 x, pii res){
    while(x <= 2*n){
        tree[x] = merge(tree[x], res);
        x += (x&-x);
    }
}
pii que(int x){
    pii ans = {0, 0};
    while(x >= 1){
        ans = merge(ans, tree[x]);
        x -= (x&-x);
    }
    return ans;
}

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(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(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: 100 / 100