oj.uz

Submission #519199

# Submission time Handle Problem Language Result Execution time Memory
519199 2022-01-26T00:59:38 Z XII trapezoid (balkan11_trapezoid) C++17
60 / 100
 93 ms 15048 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "balkan11_trapezoid"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 1e5 + 1;
const int MOD = 30013;
int n;
vector<int> Y;
using pi = pair<int, int>;
pi save[N];
vector<pair<pi, pi>> ev;

pi bit[N];

pi comb(const pi &a, const pi &b){
    return a.fi == b.fi ? mp(a.fi, (a.se + b.se) % MOD)
                        : (a.fi > b.fi) ? a : b;
}

void update(int i, const pi &v){
    while(i <= Y.size()){
        bit[i] = comb(bit[i], v);
        i += i & -i;
    }
}
pi query(int i){
    pi ans = {0, 0};
    while(1 <= i){
        ans = comb(ans, bit[i]);
        i -= i & -i;
    }
    return ans;
}

int getY(const int &y){
    return lower_bound(ALL(Y), y) - Y.begin() + 1;
}

int main(){
    IOS;
    Fi();
    cin >> n;
    Y.eb(0);
    FORU(i, 1, n){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        ev.eb(mp(a, c), mp(-1, i));
        ev.eb(mp(b, d), mp(+1, i));
        Y.eb(c), Y.eb(d);
    }
    sort(ALL(Y));
    Y.resize(unique(ALL(Y)) - Y.begin());
    sort(ALL(ev));
    pi ans = {0, 0};
    update(1, {0, 1});
    for(auto a: ev){
//        cout << a.fi.fi << " " << a.fi.se << "\n";
        if(a.se.fi == -1){
            save[a.se.se] = query(getY(a.fi.se) - 1);
            save[a.se.se].fi += 1;
            ans = comb(ans, save[a.se.se]);
        } else update(getY(a.fi.se), save[a.se.se]);
    }
    cout << ans.fi << " " << ans.se;
    return 0;
}

Compilation message

trapezoid.cpp: In function 'void update(int, const pi&)':
trapezoid.cpp:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(i <= Y.size()){
      |           ~~^~~~~~~~~~~
trapezoid.cpp: In function 'void Fi()':
trapezoid.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 5 ms 840 KB Output is correct
9 Correct 8 ms 1320 KB Output is correct
10 Correct 17 ms 2320 KB Output is correct
11 Correct 21 ms 2784 KB Output is correct
12 Correct 51 ms 5236 KB Output is correct
13 Incorrect 53 ms 5944 KB Output isn't correct
14 Incorrect 63 ms 7896 KB Output isn't correct
15 Incorrect 70 ms 7800 KB Output isn't correct
16 Incorrect 77 ms 7980 KB Output isn't correct
17 Runtime error 84 ms 14456 KB Execution killed with signal 11
18 Runtime error 75 ms 15048 KB Execution killed with signal 11
19 Incorrect 93 ms 9080 KB Output isn't correct
20 Incorrect 89 ms 9416 KB Output isn't correct