Submission #581052

#	Time	Username	Problem	Language	Result	Execution time	Memory
581052		erto	trapezoid (balkan11_trapezoid)	C++17	100 / 100	243 ms	35460 KiB

trapezoid

#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e12 + 7)
#define INF2 998244353
#define N (ll)(2e5 + 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))
#define INF3 30013

int n, g, h,m,  q,z,t1,t2, ans, ans2; 
map<int, pair<int, int>> c;
pair<pair<int, int>, pair<int, int>> p[N];
vector<pair<pair<int, int>, pair<int, int>>> v;
vector<int> v2;

pair<int, int> comb(pair<int, int> x, pair<int, int> y){
    if(x.first > y.first){
        return x;
    }
    else if(x.first < y.first){
        return y;
    }
    else{
        return {x.first, (x.second + y.second) % INF3};
    }
}

struct SegTree{
    int n;
    vector<pair<int, int>> tree;
 
    SegTree(int _n){
        n = _n+1;
        while(lsb(n) != n)
            n += lsb(n);
        tree.resize(2*n, {0, 0});
    }
 
    void update(int i, pair<int, int> val){
        i += n;
        tree[i] = val;

        while(i >>= 1){
            tree[i] = comb(tree[i * 2] , tree[i * 2 + 1]);
        }
    }
 
    pair<int, int> query(int ql, int qr){ return query(1, 0, n-1, ql, qr); }
    pair<int, int> query(int i, int lb, int rb, int ql, int qr){
        if(ql <= lb && rb <= qr){
            return tree[i];
        }
        if(qr < lb || rb < ql)
            return {0, 0};
        int md = (lb+rb)/2;
        return comb(query(2*i, lb, md, ql, qr) , query(2*i+1, md+1, rb, ql, qr));
    }
};

void solve(){
    cin >> n;
    SegTree s(N * 2);
    
    for(int i=1; i<=n; i++){
        cin >> p[i].first.first >> p[i].first.second >> p[i].second.first >> p[i].second.second;
        v.push_back({{p[i].second.first, 0}, {p[i].first.first, p[i].first.second}});
        v.push_back({{p[i].second.second, 1}, {p[i].first.first, p[i].first.second}});
        v2.push_back(p[i].first.first);
        v2.push_back(p[i].first.second);
        v2.push_back(p[i].second.first);
        v2.push_back(p[i].second.second);
    }
    v2.push_back(0);
    v2.push_back(1);
    sort(v2.begin(), v2.end());

    unique(v2.begin(), v2.end());

    for(int i=0; i<v.size(); i++){
        v[i].first.first = 1 + (lower_bound(v2.begin(), v2.end(), v[i].first.first) - v2.begin());
        v[i].second.first = 1 + (lower_bound(v2.begin(), v2.end(), v[i].second.first) - v2.begin());
        v[i].second.second = 1 + (lower_bound(v2.begin(), v2.end(), v[i].second.second) - v2.begin());
    }    
    sort(v.begin(), v.end());

    for(int i=0; i<v.size(); i++){
        if(v[i].first.second){
            g = c[v[i].second.first].first, h = c[v[i].second.first].second;
            s.update(v[i].second.second, {g, h});
        }
        else{
            pair<int, int> p2 = s.query(0ll, v[i].second.first - 1);
            g = p2.first, h = p2.second;
            g++;
            if(g > ans){
                ans = g;
                ans2 = h;
            }
            else if(g == ans){
                ans2 =  (ans2 + h) % INF3;
            }
            if(h==0)h=1;
            c[v[i].second.first] = {g, h};
        }
    }

    cout << ans << " " << ans2;
}

signed main(){
    //freopen("trapezoid.in", "r", stdin);
    //freopen("trapezoid.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

Compilation message (stderr)

trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:80:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~
trapezoid.cpp:87:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~

• Subtask 1: 100 / 100