oj.uz

Submission #581052

# Submission time Handle Problem Language Result Execution time Memory
581052 2022-06-22T08:48:38 Z erto trapezoid (balkan11_trapezoid) C++17
100 / 100
 243 ms 35460 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 10 ms 16852 KB Output is correct
4 Correct 12 ms 16828 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 18 ms 17352 KB Output is correct
7 Correct 16 ms 17492 KB Output is correct
8 Correct 19 ms 17656 KB Output is correct
9 Correct 30 ms 18532 KB Output is correct
10 Correct 53 ms 20432 KB Output is correct
11 Correct 60 ms 21432 KB Output is correct
12 Correct 114 ms 26100 KB Output is correct
13 Correct 150 ms 27984 KB Output is correct
14 Correct 190 ms 31080 KB Output is correct
15 Correct 190 ms 31036 KB Output is correct
16 Correct 232 ms 31752 KB Output is correct
17 Correct 223 ms 32792 KB Output is correct
18 Correct 205 ms 33552 KB Output is correct
19 Correct 207 ms 34536 KB Output is correct
20 Correct 243 ms 35460 KB Output is correct