oj.uz

Submission #878614

# Submission time Handle Problem Language Result Execution time Memory
878614 2023-11-25T02:01:28 Z LTTrungCHL trapezoid (balkan11_trapezoid) C++17
43 / 100
 180 ms 35396 KB 
///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
const long long e = 2023;
priority_queue <pair <pair <int ,int> ,pair <int ,int>>> q;
int n, a[N], b[N], c[N], d[N];
vector <int> duyet;
pair <int ,int> tree[N * 4];
map <int ,int> nen;
vector <pair <pair <int ,int> ,pair <int ,int>>> v;
void mer(int id){
    if (tree[id * 2].F == tree[id * 2 + 1].F){
        tree[id] = {tree[id * 2].F, (tree[id * 2].S + tree[id * 2 +1].S)%e};
    } else {
        tree[id] = max(tree[id * 2], tree[id * 2 +1]);
    }
    return;
}
void update(int id,int l,int r,int u,int val,int val2){
    if (l > u or r < u) return;
    if (l == u and r == u){
        if (tree[id].F < val){
            tree[id].F = val;
            tree[id].S = val2;
        } else if (tree[id].F == val) {
            tree[id].S += val2;
            tree[id].S %=e;
        }
        return;
    }
    int mid = (l + r)/2;
    update(id * 2,l,mid,u,val,val2);
    update(id * 2 + 1,mid + 1,r,u,val,val2);
    mer(id);
    return;
}
pair <int ,int> get(int id,int l,int r,int u,int v){
    if (l > v or r < u) return {0,0};
    if (l >= u and r <= v) return tree[id];
    int mid = (l + r)/2;
    pair <int ,int> L = get(id *2,l,mid,u,v);
    pair <int ,int> R = get(id *2 + 1,mid + 1,r,u,v);
//    cout << L.F <<" "<< R.F <<" "<<L.S <<" "<<R.S <<"\n";
    if (L.F == R.F){
        return {L.F, (L.S + R.S)%e};
    } else {
        return max(L,R);
    }
}
void inp(){
    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        duyet.pb(c[i]);
        duyet.pb(d[i]);
    }
    return;
}
void solve(){
    sort(duyet.begin(), duyet.end());
    nen[duyet[0]] = 1;
    int tt = 1;
    for (int i = 1;i < duyet.size();i++){
        if (duyet[i] > duyet[i-1]){
            ++tt;
            nen[duyet[i]] = tt;
        }
    }
    for (int i = 1;i <= n;i++){
        c[i] = nen[c[i]];
        d[i] = nen[d[i]];
        v.pb({{a[i], b[i]}, {c[i], d[i]}});
    }
    sort(v.begin(), v.end());
    update(1,0,tt,0,0,1);
//    cout << get(1,0,tt,0,tt).S <<"\n";
    for (auto x : v){
        while (!q.empty() and -q.top().F.F < x.F.F){
            update(1,0,tt,q.top().S.F,q.top().S.S,q.top().F.S);
            q.pop();
        }
        pair <int ,int> res = get(1,0,tt,0,x.S.F - 1);
        q.push({ {-x.F.S, res.S%e}, {x.S.S,res.F + 1}});
    }
    while (!q.empty()){
        update(1,0,tt,q.top().S.F,q.top().S.S,q.top().F.S);
        q.pop();
    }
    pair <int ,int> ans = get(1,0,tt,1,tt);
    cout << ans.F <<" "<< ans.S <<"\n";
    return;
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("ltt.inp", "r")){
        freopen("ltt.inp", "r", stdin);
        freopen("ltt.out", "w", stdout);
    }
    //int t;
    //cin >> t;
    //while(t--){
    inp();
    solve();
    //}
}

Compilation message

trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 1;i < duyet.size();i++){
      |                    ~~^~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("ltt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("ltt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Partially correct 2 ms 6492 KB Partially correct
3 Partially correct 2 ms 6748 KB Partially correct
4 Partially correct 2 ms 6748 KB Partially correct
5 Partially correct 3 ms 7004 KB Partially correct
6 Partially correct 4 ms 7516 KB Partially correct
7 Partially correct 6 ms 7572 KB Partially correct
8 Partially correct 8 ms 8316 KB Partially correct
9 Partially correct 18 ms 9564 KB Partially correct
10 Partially correct 27 ms 12880 KB Partially correct
11 Partially correct 35 ms 13404 KB Partially correct
12 Partially correct 78 ms 20680 KB Partially correct
13 Partially correct 92 ms 22676 KB Partially correct
14 Partially correct 128 ms 28988 KB Partially correct
15 Partially correct 127 ms 31008 KB Partially correct
16 Partially correct 140 ms 31884 KB Partially correct
17 Partially correct 141 ms 32576 KB Partially correct
18 Partially correct 144 ms 33968 KB Partially correct
19 Partially correct 149 ms 33084 KB Partially correct
20 Partially correct 180 ms 35396 KB Partially correct