oj.uz

Submission #1092235

# Submission time Handle Problem Language Result Execution time Memory
1092235 2024-09-23T15:51:05 Z NguyenPhucThang trapezoid (balkan11_trapezoid) C++17
40 / 100
 122 ms 23272 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 = 1e9 + 7;
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};
   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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 12636 KB Partially correct
2 Partially correct 2 ms 12752 KB Partially correct
3 Partially correct 3 ms 12636 KB Partially correct
4 Partially correct 4 ms 12636 KB Partially correct
5 Partially correct 5 ms 12892 KB Partially correct
6 Partially correct 6 ms 12888 KB Partially correct
7 Partially correct 6 ms 11064 KB Partially correct
8 Partially correct 8 ms 11036 KB Partially correct
9 Partially correct 12 ms 10928 KB Partially correct
10 Partially correct 22 ms 12300 KB Partially correct
11 Partially correct 28 ms 14600 KB Partially correct
12 Partially correct 53 ms 19568 KB Partially correct
13 Partially correct 62 ms 18704 KB Partially correct
14 Partially correct 78 ms 20568 KB Partially correct
15 Partially correct 89 ms 20676 KB Partially correct
16 Partially correct 95 ms 21660 KB Partially correct
17 Partially correct 101 ms 23272 KB Partially correct
18 Partially correct 84 ms 22240 KB Partially correct
19 Partially correct 96 ms 21956 KB Partially correct
20 Partially correct 122 ms 22844 KB Partially correct