Submission #445399

#	Time	Username	Problem	Language	Result	Execution time	Memory
445399		SirCovidThe19th	trapezoid (balkan11_trapezoid)	C++14	100 / 100	205 ms	10172 KiB

trapezoid

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

#define pii pair<int, int>
#define f first
#define s second

struct p{ int top, bot, type, id; }; 

int n; vector<p> pts; vector<int> mp; pii ans[100005], bit[200005]; //f - best, s - cnt

pii comb(pii a, pii b){ 
    return (a.f != b.f) ? max(a, b) : make_pair(a.f, (a.s+b.s)%30013);
}void upd(int i, pii val){
    for (; i <= mp.size(); i += i&(-i)) bit[i] = comb(bit[i], val);
}pii query(int i){
    pii ret = {0, 1};
    for (; i > 0; i -= i&(-i)) ret = comb(ret, bit[i]);
    return ret;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        pts.push_back({a, c, 1, i}); pts.push_back({b, d, -1, i});
        mp.push_back(c); mp.push_back(d);
    }sort(pts.begin(), pts.end(), [](p a, p b){ return a.top < b.top; });
    sort(mp.begin(), mp.end());
    auto conv = [&](int x){ return lower_bound(mp.begin(), mp.end(), x)-mp.begin()+1; };
    for (auto pt : pts){
        if (pt.type == 1) ans[pt.id] = query(conv(pt.bot)), ans[pt.id].f++;
        else upd(conv(pt.bot), ans[pt.id]);
    }pii res = query(mp.size()); cout<<res.f<<" "<<res.s<<endl;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void upd(int, std::pair<int, int>)':
trapezoid.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (; i <= mp.size(); i += i&(-i)) bit[i] = comb(bit[i], val);
      |            ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100