Submission #863325

#	Time	Username	Problem	Language	Result	Execution time	Memory
863325		tj14	Sails (IOI07_sails)	C++14	100 / 100	95 ms	3332 KiB

sails

#include <cstdio>
#include <algorithm>

#define pii pair<int,int>
#define ai first
#define bi second
#define ll long long

using namespace std;

const int MAXN = 100005;

struct fenwick{
  int a[MAXN];
  void update(int x, int val){
    for(int c = x ; c < MAXN ; c += c&-c)
      a[c] += val;
  }
  int query(int x){
    int ret = 0;
    for(int c = x ; c ; c -= c&-c)
      ret += a[c];
    return ret;
  }
}F;

pii A[MAXN];
ll cs[MAXN];
int N;

int main(){
  scanf("%d",&N);
  for(int c = 1 ; c <= N ; c++)
    scanf("%d %d",&A[c].ai,&A[c].bi);
  sort(A+1,A+1+N);
  for(int c = 1 ; c <= N ; c++){
    int lo = 1, hi = A[c].ai;
    int t = F.query(A[c].ai-A[c].bi+1);
    while(lo <= hi){
      int mid = (lo+hi) >> 1;
      if(F.query(mid) <= t)hi = mid-1;
      else lo = mid+1;
    }
    if(lo == A[c].ai-A[c].bi+1 or F.query(A[c].ai) == t){
      F.update(lo,1);
      F.update(lo+A[c].bi,-1);
    }
    else{
      int x = lo;
      t--;
      lo = 1, hi = A[c].ai;
      while(lo <= hi){
	int mid = (lo+hi) >> 1;
	if(F.query(mid) <= t)hi = mid-1;
	else lo = mid+1;
      }
      F.update(lo,1);
      F.update(A[c].ai+1,-1);
      F.update(x,1);
      F.update(x+(A[c].bi-(A[c].ai-lo+1)),-1);
    }
  }
  for(int c = 1 ; c < MAXN ; c++)
    cs[c] = cs[c-1]+c-1;
  ll sol = 0;
  for(int c = 1 ; c < MAXN ; c++)
    sol += cs[F.query(c)];
  printf("%lld\n",sol);
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d",&N);
      |   ~~~~~^~~~~~~~~
sails.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d %d",&A[c].ai,&A[c].bi);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10