oj.uz

답안 #1092240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092240 2024-09-23T15:53:22 Z NguyenPhucThang 사다리꼴 (balkan11_trapezoid) C++14
43 / 100
 99 ms 21516 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "trapezoid"

using namespace std;
const int base = 31;
const ll mod = 30013;
const ll oo = 1e18;
const int N = 1e6 + 5;

struct event{
   int x, y, type, idx;

   bool operator < (const event &other){
      if (x == other.x) return y < other.y;
      return x < other.x;
   }
};


pll st[4 * N];

pll combine(pll a, pll b){
   if (!a.fi && !b.fi) return {a.fi, 1};
   if (a.fi == b.fi) return {a.fi, (a.se + b.se) % mod};
   return (a.fi < b.fi ? b : a);
}

void build(int id, int l, int r){
   st[id] = {0, 1};
   if (l == r) return;
   int mid = (l + r) >> 1;
   build(2 * id, l, mid), build(2 * id + 1, mid + 1, r);
   st[id] = combine(st[2 * id], st[2 * id + 1]);
}


void update(int id, int l, int r, int i, pll v){
   if (i < l || r < i) return;
   if (l == r){
      st[id] = combine(st[id], v);
      return;
   }

   int mid = (l + r) >> 1;
   update(2 * id, l, mid, i, v), update(2 * id + 1, mid + 1, r, i, v);
   st[id] = combine(st[2 * id], st[2 * id + 1]);
}

pll get(int id, int l, int r, int u, int v){
   if (v < l || r < u) return {0, 1};
   if (u <= l && r <= v) return st[id];
   int mid = (l + r) >> 1;
   return combine(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
}

ll dp[N], cnt[N];

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int n;
   cin >> n;
   vector<event> v;
   vector<int> nen;
   forr(i, 1, n) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      if (a > b) swap(a, b);
      if (c > d) swap(c, d);  
      v.pb({a, c, 0, i});
      v.pb({b, d, 1, i});  
      nen.pb(c);
      nen.pb(d);
   }

   sort(all(nen));
   nen.resize(unique(all(nen)) - nen.begin());
   forf(i, 0, v.size()) {
      v[i].y = lower_bound(all(nen), v[i].y) - nen.begin() + 1;
   }

   forr(i, 1, n) cnt[i] = 1;
   build(1, 1, 2e5);

   sort(all(v));

   forf(i, 0, v.size()){
      if (v[i].type == 0){
         pll ans = get(1, 1, 4e5, 1, v[i].y - 1);
         int id = v[i].idx;
         dp[id] = ans.fi + 1;
         cnt[id] = ans.se;
      }
      else {
         int id = v[i].idx;
         update(1, 1, 4e5, v[i].y, {dp[id], cnt[id]});
      }
   }  


   int res_dp = 0, res_cnt;
   forr(i, 1, n) if (res_dp < dp[i]) res_dp = dp[i], res_cnt = cnt[i];
   cout << res_dp << " " << res_cnt;

   return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
trapezoid.cpp:96:4: note: in expansion of macro 'forf'
   96 |    forf(i, 0, v.size()) {
      |    ^~~~
trapezoid.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
trapezoid.cpp:105:4: note: in expansion of macro 'forf'
  105 |    forf(i, 0, v.size()){
      |    ^~~~
trapezoid.cpp:121:29: warning: 'res_cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |    cout << res_dp << " " << res_cnt;
      |                             ^~~~~~~

Subtask #1
43.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 12636 KB Partially correct
2 Partially correct 2 ms 12636 KB Partially correct
3 Partially correct 3 ms 12812 KB Partially correct
4 Partially correct 3 ms 12636 KB Partially correct
5 Partially correct 4 ms 12892 KB Partially correct
6 Partially correct 5 ms 12892 KB Partially correct
7 Partially correct 6 ms 12892 KB Partially correct
8 Partially correct 7 ms 13184 KB Partially correct
9 Partially correct 12 ms 13168 KB Partially correct
10 Partially correct 19 ms 13844 KB Partially correct
11 Partially correct 25 ms 16148 KB Partially correct
12 Partially correct 52 ms 18436 KB Partially correct
13 Correct 61 ms 19132 KB Output is correct
14 Partially correct 69 ms 20712 KB Partially correct
15 Partially correct 78 ms 21248 KB Partially correct
16 Partially correct 83 ms 21516 KB Partially correct
17 Partially correct 86 ms 21140 KB Partially correct
18 Partially correct 79 ms 21496 KB Partially correct
19 Partially correct 90 ms 20472 KB Partially correct
20 Partially correct 99 ms 21468 KB Partially correct