oj.uz

Submission #445399

# Submission time Handle Problem Language Result Execution time Memory
445399 2021-07-17T23:57:07 Z SirCovidThe19th trapezoid (balkan11_trapezoid) C++14
100 / 100
 205 ms 10172 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 8 ms 716 KB Output is correct
8 Correct 9 ms 768 KB Output is correct
9 Correct 21 ms 1200 KB Output is correct
10 Correct 38 ms 2304 KB Output is correct
11 Correct 50 ms 2748 KB Output is correct
12 Correct 101 ms 5244 KB Output is correct
13 Correct 122 ms 6120 KB Output is correct
14 Correct 145 ms 7580 KB Output is correct
15 Correct 157 ms 7932 KB Output is correct
16 Correct 170 ms 8356 KB Output is correct
17 Correct 184 ms 8872 KB Output is correct
18 Correct 171 ms 9252 KB Output is correct
19 Correct 194 ms 9640 KB Output is correct
20 Correct 205 ms 10172 KB Output is correct