oj.uz

Submission #106010

# Submission time Handle Problem Language Result Execution time Memory
106010 2019-04-16T07:52:23 Z MrTEK trapezoid (balkan11_trapezoid) C++14
0 / 100
 8 ms 1920 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 5e3 + 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 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 6 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 6 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 7 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 5 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 6 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 5 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 4 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 5 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 3 ms 1092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 4 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 5 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)