oj.uz

Submission #254121

# Submission time Handle Problem Language Result Execution time Memory
254121 2020-07-29T11:37:52 Z Nucleist Tenis (COI19_tenis) C++14
21 / 100
 497 ms 6560 KB 
//Self-control leads to consistency.
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
ll seg[400011];
ll arr[400011],ari[400011];
void upd(ll p,ll l,ll r,ll k,ll val){
  if(l==r && l==k){
    seg[p]=max(seg[p],val);
    return;
  }
  ll med=(l+r)>>1;
  if(k<=med){
    upd(p*2,l,med,k,val);
  }
  else upd(p*2+1,med+1,r,k,val);
  seg[p]=max(seg[p*2],seg[p*2+1]);
}
ll query(ll p,ll l,ll r,ll l1,ll r1){
  if(l>r || l>r1 || l1>r)return 0;
  if(l>=l1 && r<=r1)return seg[p];
  ll med=(l+r)>>1;
  return max(query(p*2,l,med,l1,r1),query(p*2+1,med+1,r,l1,r1));
}
int main()
{
  //flash;
  ll n,q;
  cin>>n>>q;
  for (ll i = 0; i < n; ++i)
  {
    ll yo;
    cin>>yo;
    yo--;
    arr[yo]=i;
    ari[i]=yo;
    upd(1,0,n-1,i,i);
  }
  for (ll i = 0; i < n; ++i)
  {
    ll yo;
    cin>>yo;
    yo--;
    upd(1,0,n-1,arr[yo],i);
  }
  for (ll i = 0; i < n; ++i)
  {
    ll yo;
    cin>>yo;
    yo--;
    upd(1,0,n-1,arr[yo],i);
  }
  ll l=0,r=0;
  set<ll>ans;
  while(query(1,0,n-1,l,r)+1!=(r-l+1)){
    ll cur=query(1,0,n-1,l,r);
    r++;
  }
  for (ll i = 0; i <= r; ++i)
  {
    ans.insert(ari[i]);
  }
  while(q--){
    ll na;
    cin>>na;
    if(na==1){
      ll x;
      cin>>x;
      x--;
      if(ans.find(x)!=ans.end()){
        cout<<"DA"<<'\n';
      }
      else cout<<"NE"<<'\n';
    }
    else{

    }
  }
  return 0;
}

Compilation message

tenis.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
tenis.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
tenis.cpp: In function 'int main()':
tenis.cpp:82:8: warning: unused variable 'cur' [-Wunused-variable]
     ll cur=query(1,0,n-1,l,r);
        ^~~
tenis.cpp: In function 'void setIO(std::__cxx11::string)':
tenis.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".in").c_str(),"r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tenis.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".out").c_str(),"w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 6560 KB Output is correct
2 Correct 424 ms 4600 KB Output is correct
3 Correct 436 ms 4344 KB Output is correct
4 Correct 424 ms 4260 KB Output is correct
5 Correct 431 ms 4344 KB Output is correct
6 Correct 420 ms 4348 KB Output is correct
7 Correct 424 ms 4216 KB Output is correct
8 Correct 417 ms 4344 KB Output is correct
9 Correct 415 ms 4472 KB Output is correct
10 Correct 415 ms 4472 KB Output is correct
11 Correct 427 ms 5240 KB Output is correct
12 Correct 421 ms 4344 KB Output is correct
13 Correct 425 ms 4344 KB Output is correct
14 Correct 433 ms 4472 KB Output is correct
15 Correct 432 ms 4344 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -