oj.uz

Submission #581043

# Submission time Handle Problem Language Result Execution time Memory
581043 2022-06-22T08:44:46 Z erto trapezoid (balkan11_trapezoid) C++17
61 / 100
 239 ms 38148 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))

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};
    }
}

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 += h;
            }
            if(h==0)h=1;
            c[v[i].second.first] = {g, h};
        }
    }
    ans2 %= 30013;

    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:79: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]
   79 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~
trapezoid.cpp:86: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]
   86 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
61.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16764 KB Output is correct
3 Correct 9 ms 16856 KB Output is correct
4 Partially correct 9 ms 16940 KB Partially correct
5 Correct 11 ms 17176 KB Output is correct
6 Partially correct 14 ms 17372 KB Partially correct
7 Partially correct 14 ms 17492 KB Partially correct
8 Correct 19 ms 17784 KB Output is correct
9 Correct 27 ms 18768 KB Output is correct
10 Partially correct 46 ms 21016 KB Partially correct
11 Partially correct 56 ms 22156 KB Partially correct
12 Partially correct 126 ms 27412 KB Partially correct
13 Partially correct 136 ms 29588 KB Partially correct
14 Partially correct 168 ms 32980 KB Partially correct
15 Partially correct 183 ms 32916 KB Partially correct
16 Correct 200 ms 33848 KB Output is correct
17 Partially correct 224 ms 34980 KB Partially correct
18 Partially correct 205 ms 36140 KB Partially correct
19 Partially correct 201 ms 37168 KB Partially correct
20 Partially correct 239 ms 38148 KB Partially correct