oj.uz

답안 #467519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467519 2021-08-23T12:21:03 Z Vladth11 사다리꼴 (balkan11_trapezoid) C++14
62 / 100
 394 ms 19116 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;

class All{
public:
    pii all[4 * NMAX];
    pii combine(pii a, pii b){
        if(a.first > b.first)
            return a;
        if(a.first < b.first)
            return b;
        return {a.first, (a.second + b.second) % MOD};
    }
    void update(ll node, ll st, ll dr, ll a, pii b){
        if(st == dr){
            all[node] = b;
            return;
        }
        ll mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        all[node] = combine(all[node * 2], all[node * 2 + 1]);
    }
    pii query(ll node, ll st, ll dr, ll a, ll b){
        if(a <= st && dr <= b){
            return all[node];
        }
        ll mid = (st + dr) / 2;
        pii rez = {-1, 0};
        if(a <= mid){
            rez = combine(rez, query(node * 2, st, mid, a, b));
        }
        if(b > mid){
            rez = combine(rez, query(node * 2 + 1, mid + 1, dr, a, b));
        }
        return rez;
    }
    void set(ll a, pii b){
        update(1, 1, NMAX - 1, a, b);
    }
    pii prefix(ll x){
        return query(1, 1, NMAX - 1, 1, x); ///sa evit 0
    }
}st;

struct ura{
    ll a, b, c, d;
};

bool cmp(ura a, ura b){
    return a.a < b.a;
}

pii dp[100001];
ura v[100001];

vector <ll> nrm;
map <ll, ll> mp;

int main() {
    ll n, i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
        nrm.push_back(v[i].a);
        nrm.push_back(v[i].b);
    }
    ///normalizare
    ll cnt = 0;
    sort(nrm.begin(), nrm.end());
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }
    nrm.clear();
    for(i = 1; i <= n; i++){
        v[i].a = mp[v[i].a];
        v[i].b = mp[v[i].b];
          nrm.push_back(v[i].c);
        nrm.push_back(v[i].d);
    }
    mp.clear();
    sort(nrm.begin(), nrm.end());
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }
    nrm.clear();
     for(i = 1; i <= n; i++){
        v[i].c = mp[v[i].c];
        v[i].d = mp[v[i].d];
    }
    mp.clear();
    ///gata
    sort(v + 1, v + n + 1, cmp);
    priority_queue <pii> pq; ///daca sortez dupa b, scot logul
    pii sol = {0, 0};
    st.set(1, {0, 1});
    for(i = 1; i <= n; i++){
        while(pq.size() && (-pq.top().first) <= v[i].a){
            st.set(v[pq.top().second].d, dp[pq.top().second]);
            pq.pop();
        }
        dp[i] = st.prefix(v[i].c);
        dp[i].first++;
        pq.push({-v[i].b, i});
        sol = st.combine(sol, dp[i]);
    }
    cout << sol.first << " " << sol.second << "\n";
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:93:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~
trapezoid.cpp:107:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~

Subtask #1
62.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 7 ms 844 KB Output is correct
6 Correct 10 ms 1100 KB Output is correct
7 Correct 13 ms 1372 KB Output is correct
8 Correct 17 ms 1612 KB Output is correct
9 Correct 35 ms 3040 KB Output is correct
10 Correct 73 ms 5692 KB Output is correct
11 Correct 96 ms 6808 KB Output is correct
12 Correct 212 ms 13748 KB Output is correct
13 Incorrect 251 ms 14852 KB Output isn't correct
14 Incorrect 292 ms 15988 KB Output isn't correct
15 Incorrect 343 ms 16408 KB Output isn't correct
16 Incorrect 357 ms 16924 KB Output isn't correct
17 Partially correct 372 ms 17492 KB Partially correct
18 Incorrect 362 ms 17844 KB Output isn't correct
19 Incorrect 375 ms 18448 KB Output isn't correct
20 Incorrect 394 ms 19116 KB Output isn't correct