oj.uz

Submission #863325

# Submission time Handle Problem Language Result Execution time Memory
863325 2023-10-20T03:18:22 Z tj14 Sails (IOI07_sails) C++14
100 / 100
 95 ms 3332 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 26 ms 1628 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2268 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3008 KB Output is correct
2 Correct 45 ms 2888 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3200 KB Output is correct
2 Correct 63 ms 2832 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3332 KB Output is correct
2 Correct 38 ms 3068 KB Output is correct