oj.uz

Submission #370745

# Submission time Handle Problem Language Result Execution time Memory
370745 2021-02-24T14:21:07 Z Atill83 Sirni (COCI17_sirni) C++14
140 / 140
 3195 ms 661288 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)

typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAXN = 1<<19, MAXM = 1e7 + 5;

vector <P> V[MAXM];
int najbliz[MAXM];
int p[MAXN];
int n;
int root[MAXN], rnk[MAXN];
int bio[MAXM], ozn[MAXM];

int find(int x)
{
  if (root[x] == -1) return x;
  return root[x] = find(root[x]);
}

void merge(int a, int b)
{
  a = find(a);
  b = find(b);
  assert(a != b);

  if (rnk[a] > rnk[b]) root[b] = a;
  else if (rnk[b] > rnk[a]) root[a] = b;
  else {
    rnk[a]++;
    root[b] = a;
  }
}

int main()
{
  #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
  #endif
  scanf("%d", &n);
  memset(ozn, -1, sizeof ozn);
  REP(i, n) {
    scanf("%d", &p[i]);
    najbliz[p[i]] = p[i];
    if (ozn[p[i]] == -1)
      ozn[p[i]] = i;
  }

  for (int i=MAXM-2; i>=0; i--)
    if (!najbliz[i])
      najbliz[i] = najbliz[i+1];

  REP(i, n) {
    if (bio[p[i]]++) continue;
    if (najbliz[p[i]+1]) {
      if (2*p[i] >= MAXM || najbliz[2*p[i]] != najbliz[p[i]+1])
        V[najbliz[p[i]+1] - p[i]].push_back(P(i, ozn[najbliz[p[i]+1]]));
    }

    for (int j=2*p[i]; j<MAXM && najbliz[j]; j+=p[i])
      if (j + p[i] >= MAXM || najbliz[j+p[i]] != najbliz[j])
        V[najbliz[j]-j].push_back(P(i, ozn[najbliz[j]]));
  }

  memset(root, -1, sizeof root);
  ll rje = 0;
  int top = 0;
  REP(i, MAXM){
    top += V[i].size();
    REP(j, (int) V[i].size())
    if (find(V[i][j].X) != find(V[i][j].Y)) {
      merge(V[i][j].X, V[i][j].Y);
      rje += i;
    }
  }
  REP(i, n) if (ozn[p[i]] == i) { assert(find(i) == find(0)); }
  cerr<<top<<endl;
  printf("%lld\n", rje);

  return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
sirni.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d", &p[i]);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 319340 KB Output is correct
2 Correct 314 ms 320364 KB Output is correct
3 Correct 272 ms 319596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 315756 KB Output is correct
2 Correct 587 ms 316840 KB Output is correct
3 Correct 264 ms 319852 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 319596 KB Output is correct
2 Correct 258 ms 318060 KB Output is correct
3 Correct 260 ms 319596 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 330116 KB Output is correct
2 Correct 518 ms 356436 KB Output is correct
3 Correct 372 ms 335420 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 321260 KB Output is correct
2 Correct 422 ms 342124 KB Output is correct
3 Correct 342 ms 328628 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 341372 KB Output is correct
2 Correct 567 ms 367956 KB Output is correct
3 Correct 375 ms 333100 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 320064 KB Output is correct
2 Correct 560 ms 367008 KB Output is correct
3 Correct 365 ms 332436 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 368364 KB Output is correct
2 Correct 1895 ms 568600 KB Output is correct
3 Correct 442 ms 371048 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 368248 KB Output is correct
2 Correct 3002 ms 661288 KB Output is correct
3 Correct 476 ms 375008 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 352236 KB Output is correct
2 Correct 3195 ms 651088 KB Output is correct
3 Correct 381 ms 335260 KB Output is correct