oj.uz

Submission #106012

# Submission time Handle Problem Language Result Execution time Memory
106012 2019-04-16T07:53:01 Z MrTEK trapezoid (balkan11_trapezoid) C++14
0 / 100
 132 ms 32764 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;
const int mod = 30013;
const int inf = 1e9;

#define ul first.first
#define ur first.second
#define dl second.first
#define dr second.second

pair <ii,ii> a[N];
int n;
ii ans,dp[N],tree[N << 3];
map <int,int> ind;
vector <int> v,updates[N];

int add(int x,int y) {
  return x + y >= mod ? x + y - mod : x + y;
}

ii merge(ii x,ii y) {
  if (x.first == y.first)
    return {x.first,add(x.second,y.second)};
  if (x.first > y.first)
    return x;
  return y;
}

ii query(int ind,int l,int r,int lw,int rw) {
  if (l > rw || r < lw)
    return {-inf,-inf};
  if (l >= lw && r <= rw)
    return tree[ind];
  int mid = (l + r) / 2;
  return merge(query(ind + ind,l,mid,lw,rw),query(ind + ind + 1,mid + 1,r,lw,rw));
}

void update(int ind,int l,int r,int w,ii val) {
  if (l > w || r < w)
    return;
  if (l == w && r == w) {
    tree[ind] = merge(tree[ind],val);
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind,l,mid,w,val);
  update(ind + ind + 1,mid + 1,r,w,val);
  tree[ind] = merge(tree[ind + ind],tree[ind + ind + 1]);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
    v.push_back(a[i].dl);
    v.push_back(a[i].dr);
  }
  sort(v.begin(),v.end());
  for (int i = 0 , j = 0 ; i < v.size() ; i++) {
    if (i == 0 || v[i] != v[i - 1])
      j++;
    ind[v[i]] = j;
  }
  sort(a + 1,a + n + 1);
  for (int i = 1 ; i < (N << 3) ; i++)
    dp[i] = {-inf,-inf};
  for (int i = n , j = n ; i >= 1 ; i--) {
    for (auto k : updates[i])
      update(1,1,2 * n,ind[a[k].dl],dp[k]);    
    dp[i] = {1,1};
    ii tut = query(1,1,2 * n,ind[a[i].dr],2 * n);
    tut.first++;
    dp[i] = merge(dp[i],tut);
    while(j > 0 && a[j].ur >= a[i].ul)
      j--;
    ans = merge(ans,dp[i]);
    updates[j].push_back(i);
  }
  cout << ans.first << " " << ans.second << endl;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:67:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0 , j = 0 ; i < v.size() ; i++) {
                            ~~^~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 14 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 15 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 13 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 15 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 15 ms 10496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 20 ms 10612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 18 ms 10880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 24 ms 12024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 34 ms 14200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 46 ms 15352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 71 ms 21092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 87 ms 23536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 100 ms 25948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 127 ms 26944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 117 ms 28016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 127 ms 29376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 132 ms 30316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 128 ms 31580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 129 ms 32764 KB Execution killed with signal 11 (could be triggered by violating memory limits)