oj.uz

답안 #467521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467521 2021-08-23T12:23:18 Z Vladth11 사다리꼴 (balkan11_trapezoid) C++14
82 / 100
 433 ms 23964 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 = 300001;
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){
          	b.second %= MOD;
            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[300001];
ura v[300001];

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:94: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]
   94 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~
trapezoid.cpp:108: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]
  108 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~

Subtask #1
82.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 972 KB Output is correct
6 Correct 10 ms 1256 KB Output is correct
7 Correct 13 ms 1484 KB Output is correct
8 Correct 18 ms 1740 KB Output is correct
9 Correct 35 ms 3320 KB Output is correct
10 Correct 71 ms 6296 KB Output is correct
11 Correct 97 ms 7436 KB Output is correct
12 Correct 203 ms 15176 KB Output is correct
13 Correct 270 ms 18344 KB Output is correct
14 Correct 297 ms 20888 KB Output is correct
15 Correct 356 ms 22616 KB Output is correct
16 Correct 359 ms 22832 KB Output is correct
17 Partially correct 398 ms 23344 KB Partially correct
18 Incorrect 372 ms 23468 KB Output isn't correct
19 Incorrect 405 ms 22944 KB Output isn't correct
20 Incorrect 433 ms 23964 KB Output isn't correct