oj.uz

Submission #756536

# Submission time Handle Problem Language Result Execution time Memory
756536 2023-06-11T19:44:08 Z michao Advertisement 2 (JOI23_ho_t2) C++14
100 / 100
 683 ms 65568 KB 
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int inf=(int)1e18+9;
const int MAX=1<<19;
pii t[MAX*2][2];
pii merguj(pii x,pii y){
  if (x.st<=y.st)return x;
  return y;
}
int x[MAX],e[MAX];
bool cmp(int i,int j){
  if (e[i]!=e[j])return e[i]>e[j];
  return x[i]<x[j];
}

void update(int u,int c,int pos,int id){
  u+=MAX;
  t[u][id]=mp(c,pos);
  for (;u>1;u>>=1)t[u>>1][id]=merguj(t[u][id],t[u^1][id]);
}

pii query(int u,int v,int id){
  pii wyn=mp(inf,inf);
  for (u+=MAX,v+=MAX+1;u<v;u>>=1,v>>=1){
    if (u&1)wyn=merguj(wyn,t[u++][id]);
    if (v&1)wyn=merguj(wyn,t[--v][id]);
  }
  return wyn;
}
bool O[MAX];
bool check(int i,int j){
  return e[i]-e[j]>=abs(x[i]-x[j]);
}
int beka[MAX];
bool cmp2(int i,int j){
  if (x[i]!=x[j])return x[i]<x[j];
  return e[i]<e[j];
}
int idx[MAX];
int re[MAX];
int32_t main()
{
  BOOST;
  int n;
  cin>>n;
  vi pom;
  for (int i=1;i<=n;i++)pom.pb(i);
  for (int i=1;i<=n;i++)cin>>x[i]>>e[i];
  for (int i=1;i<=n;i++)beka[i]=i;
  sort(beka+1,beka+n+1,cmp2);
  for (int i=1;i<=n;i++)idx[beka[i]]=i,re[i]=beka[i];
  for (int i=1;i<=n;i++){
    update(idx[i],e[i]-x[i],idx[i],0);
    update(idx[i],e[i]+x[i],idx[i],1);
  }
  sort(pom.begin(),pom.end(),cmp);
  int ans=0;
  for (auto it:pom){
    if (O[idx[it]])continue;
   // cout<<"TERAZ "<<idx[it]<<"\n";
    O[idx[it]]=true;
    update(idx[it],inf,inf,0);
    update(idx[it],inf,inf,1);
    ans++;
    int l=idx[it]+1,r=n;
    if (l<=r){
      while (true){
        pii ask=query(l,r,1);
        if (ask.st>e[it]+x[it])break;
        int id=ask.nd;
       /* cout<<"TERAZ "<<it<<" "<<ask.st<<" "<<re[id]<<" "<<idx[it]<<" "<<id<<"\n";
        if (!check(it,re[id])){
          cout<<"KONIEC\n";
          return 0LL;
        }*/
        O[id]=true;
        update(id,inf,inf,0);
        update(id,inf,inf,1);
      }
    }
    l=1,r=idx[it]-1;
    if (l<=r){
      while (true){
        pii ask=query(l,r,0);
        if (ask.st>e[it]-x[it])break;
        int id=ask.nd;
        O[id]=true;
        /*
        cout<<"TERAZ "<<it<<" "<<re[id]<<" "<<idx[it]<<" "<<id<<"\n";
        if (!check(it,re[id])){
          cout<<"KONIEC\n";
          return 0LL;
        }*/
        update(id,inf,inf,0);
        update(id,inf,inf,1);
      }
    }
  }
  cout<<ans;
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 136 ms 14784 KB Output is correct
3 Correct 192 ms 20292 KB Output is correct
4 Correct 443 ms 51592 KB Output is correct
5 Correct 191 ms 39944 KB Output is correct
6 Correct 683 ms 62544 KB Output is correct
7 Correct 641 ms 58700 KB Output is correct
8 Correct 490 ms 65552 KB Output is correct
9 Correct 289 ms 62400 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #3
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 136 ms 14784 KB Output is correct
3 Correct 192 ms 20292 KB Output is correct
4 Correct 443 ms 51592 KB Output is correct
5 Correct 191 ms 39944 KB Output is correct
6 Correct 683 ms 62544 KB Output is correct
7 Correct 641 ms 58700 KB Output is correct
8 Correct 490 ms 65552 KB Output is correct
9 Correct 289 ms 62400 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 408 ms 42832 KB Output is correct
37 Correct 544 ms 53960 KB Output is correct
38 Correct 627 ms 63032 KB Output is correct
39 Correct 647 ms 60008 KB Output is correct
40 Correct 647 ms 65380 KB Output is correct
41 Correct 625 ms 63744 KB Output is correct
42 Correct 531 ms 65568 KB Output is correct
43 Correct 602 ms 59304 KB Output is correct
44 Correct 536 ms 64912 KB Output is correct
45 Correct 649 ms 59888 KB Output is correct