oj.uz

Submission #225256

# Submission time Handle Problem Language Result Execution time Memory
225256 2020-04-20T02:21:25 Z FieryPhoenix Sails (IOI07_sails) C++11
15 / 100
 1000 ms 9044 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int H[100001],K[100001];
vector<pair<int,int>>v;

struct LazySegmentTree{
  int siz;
  vector<ll>tree,lazy;
  LazySegmentTree(int temp){
    siz=temp;
    while ((siz&(siz-1))!=0) siz++;
    for (int i=0;i<siz*2;i++){
      tree.push_back(0);
      lazy.push_back(0);
    }
  }
  LazySegmentTree(){}
  void build(int pos, ll x){
    pos+=siz;
    tree[pos]=x;
    for (pos/=2;pos>=1;pos/=2)
      tree[pos]+=x;
  } 
  void propagate(int node, int L, int R){
    tree[node]+=lazy[node]*(R-L+1);
    if (L!=R){
      lazy[node*2]+=lazy[node];
      lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
  }
  void update(int node, int L, int R, int i, int j, ll x){
    propagate(node,L,R);
    if (L>R || L>j || R<i)
      return;
    if (L>=i && R<=j){
      lazy[node]+=x;
      propagate(node,L,R);
      return;
    }
    update(node*2,L,(L+R)/2,i,j,x);
    update(node*2+1,(L+R)/2+1,R,i,j,x);
    tree[node]=tree[node*2]+tree[node*2+1];
  }
  ll query(int node, int L, int R, int i,int j){
    if (L>R || L>j || R<i)
      return 0;
    propagate(node,L,R);
    if (L>=i && R<=j)
      return tree[node];
    ll q1=query(node*2,L,(L+R)/2,i,j);
    ll q2=query(node*2+1,(L+R)/2+1,R,i,j);
    return q1+q2;
  }
  ll query(int i, int j){ return query(1,0,siz-1,i,j); }
  void update(int i, int j, ll val){ update(1,0,siz-1,i,j,val); }
};

struct BIT{
  vector<ll>tree;
  int size;
  BIT(){}
  BIT(int n){
    size=n;
    for (int i=0;i<=n;i++)
      tree.push_back(0);
  }
  ll sum(int x){
    ll s=0;
    while (x>=1){
      s+=tree[x];
      x-=(x&-x);
    }
    return s;
  }
  void update(int x, int k){
    if (x==0) return;
    while (x<=size){
      tree[x]+=k;
      x+=(x&-x);
    }
  }
  ll query(int l, int r){
    return sum(r)-((l==0)?0:sum(l-1));
  }
};

LazySegmentTree lst;
BIT bit;
int L,R;

void addZero(int num){
  if (num==0) return;
  if (lst.query(L,L)==0)
    bit.update(L,-1);
  L-=num;
  bit.update(L,1);
}

int getFirst(int val){
  int low=L-1,high=R+1,mid;
  while (low+1<high){
    mid=(low+high)/2;
    if (bit.sum(mid)>=val)
      high=mid;
    else
      low=mid;
  }
  return high;
}

void increment(int num){
  int k=bit.query(0,L+num-1);
  int i=getFirst(k);
  int j=getFirst(k+1);
  int len=L+num-1-i+1;
  //cout<<i<<' '<<j<<' '<<len<<endl;
  lst.update(L,i-1,1);
  lst.update(j-len,j-1,1);
  if (j-len!=L && lst.query(j-len,j-len)!=lst.query(j-len-1,j-len-1))
    bit.update(j-len,1);
  if (lst.query(j,j)==lst.query(j-1,j-1))
    bit.update(j,-1);
  if (i!=L && lst.query(i,i)==lst.query(i-1,i-1))
    bit.update(i,-1);
}

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  int N;
  cin>>N;
  lst=LazySegmentTree(N+5);
  bit=BIT(N+5);
  for (int i=0;i<N;i++){
    cin>>H[i]>>K[i];
    v.push_back({H[i],K[i]});
  }
  sort(v.begin(),v.end());
  R=N;
  L=N+1;
  for (int i=0;i<N;i++){
    //cout<<"PROCESS "<<v[i].first<<' '<<v[i].second<<endl;
    int prevH=0;
    if (i>0) prevH=v[i-1].first;
    addZero(v[i].first-prevH);
    increment(v[i].second);
    /*
    for (int i=1;i<=N;i++)
      cout<<lst.query(i,i)<<' ';
    cout<<endl;
    for (int i=1;i<=N;i++)
      cout<<bit.query(i,i)<<' ';
    cout<<endl;
    */
  }
  ll ans=0;
  for (int i=1;i<=N;i++){
    ll x=lst.query(i,i);
    ans+=(x*(x-1))/2;
  }
  cout<<ans<<endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 2676 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 4580 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 8144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 8664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 471 ms 9044 KB Output isn't correct
2 Halted 0 ms 0 KB -