Submission #1171774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171774		Hanksburger	trapezoid (balkan11_trapezoid)	C++20	100 / 100	114 ms	16032 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int, int>, pair<int, int> > > rect;
pair<int, int> bit[200005], ans[100005], ANS;
vector<pair<pair<int, int>, int> > event;
map<int, int> mp;
int n, cnt;
pair<int, int> merge(pair<int, int> x, pair<int, int> y)
{
    if (x.first!=y.first)
        return x.first>y.first?x:y;
    return {x.first, (x.second+y.second)%30013};
}
void upd(int x, pair<int, int> y)
{
    for (int i=x; i<=cnt; i+=i&(-i))
        bit[i]=merge(bit[i], y);
}
pair<int, int> qry(int x)
{
    pair<int, int> res={0, 0};
    for (int i=x; i; i-=i&(-i))
        res=merge(res, bit[i]);
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    mp[0]=1;
    for (int i=0; i<n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        rect.push_back({{a, b}, {c, d}});
        event.push_back({{a, 1}, i});
        event.push_back({{b, 0}, i});
        mp[c]=mp[d]=1;
    }
    for (auto it=mp.begin(); it!=mp.end(); it++)
        it->second=(++cnt);
    upd(1, {0, 1});
    sort(event.begin(), event.end());
    for (int i=0; i<event.size(); i++)
    {
        int ind=event[i].second;
        if (event[i].first.second)
        {
            ans[ind]=qry(mp[rect[ind].second.first]-1);
            ans[ind].first++;
            ANS=merge(ANS, ans[ind]);
        }
        else
            upd(mp[rect[ind].second.second], ans[ind]);
    }
    cout << ANS.first << ' ' << ANS.second;
}

• Subtask 1: 100 / 100