Submission #225256

#	Time	Username	Problem	Language	Result	Execution time	Memory
225256		FieryPhoenix	Sails (IOI07_sails)	C++11	15 / 100	1099 ms	9044 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10