oj.uz

Submission #313703

# Submission time Handle Problem Language Result Execution time Memory
313703 2020-10-16T18:57:14 Z tushar_2658 trapezoid (balkan11_trapezoid) C++14
100 / 100
 379 ms 28920 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 200505;
using ll = long long;
ll mod = 30013;

struct Data {
  int l1, r1, l2, r2;
};
Data p[maxn];
int n;

struct DATA {
  int val, cnt;
  DATA (int val, int cnt) : val(val), cnt(cnt){}
  DATA(){}
};

DATA t[maxn << 2], dp[maxn];
int state[maxn];

DATA join(DATA l, DATA r){
  DATA ret;
  if(l.val > r.val)ret = l;
  else if(l.val < r.val)ret = r;
  else {
    ret.val = l.val;
    ret.cnt = (l.cnt + r.cnt) % mod;
  }
  return ret;
}

void upd(int node, int b, int e, int idx, DATA val){
  if(idx > e or idx < b)return;
  if(b == idx && idx == e){
    t[node] = val;
    return;
  }
  int mid = (b + e) >> 1;
  if(idx <= mid)upd(2*node, b, mid, idx, val);
  else upd(2*node + 1, mid + 1, e, idx, val);
  t[node] = join(t[2*node], t[2*node + 1]);
}

DATA query(int node, int b, int e, int i, int j){
  if(i > e or j < b)return DATA(0, 0);
  if(b >= i && j >= e)return t[node];
  int mid = (b + e) >> 1;
  return join(query(2*node, b, mid, i, j), query(2*node + 1, mid + 1, e, i, j));
}

int main(int argc, char const *argv[])
{
  scanf("%d", &n);
  map<int, int> mp, mp1;
  for(int i = 1; i <= n; ++i){
    scanf("%d %d %d %d", &p[i].l1, &p[i].r1, &p[i].l2, &p[i].r2);
    mp[p[i].l1];
    mp[p[i].r1];
    mp1[p[i].l2];
    mp1[p[i].r2];
  }
  int cnt = 0;
  for(auto& i : mp){
    i.second = ++cnt;
  }
  cnt = 0; 
  for(auto& i : mp1){
    i.second = ++cnt;
  }
  for(int i = 1; i <= n; ++i){
    p[i].l1 = mp[p[i].l1];
    p[i].r1 = mp[p[i].r1];
    p[i].l2 = mp1[p[i].l2];
    p[i].r2 = mp1[p[i].r2];
  }
  for(int i = 1; i <= n; ++i){
    state[p[i].l1] = i;
    state[p[i].r1] = -i;
  }  
  for(int i = 1; i <= (n << 1); ++i){
    int x = abs(state[i]);
    if(state[i] < 0){
      upd(1, 1, cnt, p[x].r2, dp[x]);
    }else {
      dp[x] = query(1, 1, cnt, 1, p[x].l2 - 1);
      dp[x].val++;
      if(dp[x].val == 1){
        dp[x].cnt = 1;
      }
    }
  }
  DATA ans(0, 0);
  for(int i = 1; i <= n; ++i){
    ans = join(ans, dp[i]);
  }
  cout << ans.val << ' ' << ans.cnt << endl;

  return 0;
}

Compilation message

trapezoid.cpp: In function 'int main(int, const char**)':
trapezoid.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
trapezoid.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     scanf("%d %d %d %d", &p[i].l1, &p[i].r1, &p[i].l2, &p[i].r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 9 ms 1408 KB Output is correct
8 Correct 13 ms 1664 KB Output is correct
9 Correct 27 ms 3072 KB Output is correct
10 Correct 53 ms 5752 KB Output is correct
11 Correct 75 ms 6776 KB Output is correct
12 Correct 169 ms 13368 KB Output is correct
13 Correct 217 ms 15608 KB Output is correct
14 Correct 251 ms 19704 KB Output is correct
15 Correct 301 ms 20888 KB Output is correct
16 Correct 350 ms 22008 KB Output is correct
17 Correct 333 ms 25452 KB Output is correct
18 Correct 276 ms 24056 KB Output is correct
19 Correct 331 ms 27192 KB Output is correct
20 Correct 379 ms 28920 KB Output is correct