oj.uz

Submission #254136

# Submission time Handle Problem Language Result Execution time Memory
254136 2020-07-29T11:57:02 Z Nucleist Tenis (COI19_tenis) C++14
39 / 100
 500 ms 9336 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 ari[400011];
pair<int,dos> zi[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--;
    ari[i]=yo;
    zi[yo].first=i;
  }
  for (ll i = 0; i < n; ++i)
  {
    ll yo;
    cin>>yo;
    yo--;
    zi[yo].second.first=i;
  }
  for (ll i = 0; i < n; ++i)
  {
    ll yo;
    cin>>yo;
    yo--;
    zi[yo].second.second=i;
  }
  for (int i = 0; i < n; ++i)
  {
    upd(1,0,n-1,zi[i].first,max(zi[i].second.first,zi[i].second.second));
  }
  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{
      int x,y,z;
      cin>>x>>y>>z;
      y--,z--;
      if(x==1){
        ari[zi[y].first]=z;
        ari[zi[z].first]=y;
        swap(zi[y].first,zi[z].first);
      }
      if(x==2)swap(zi[y].second.first,zi[z].second.first);
      if(x==3)swap(zi[y].second.second,zi[z].second.second);
      memset(seg,0,sizeof seg);
      for (int i = 0; i < n; ++i)
      {
        upd(1,0,n-1,zi[i].first,max(zi[i].second.first,zi[i].second.second));
      }
      ll l1=0,r1=0;
      ans.clear();
      while(query(1,0,n-1,l1,r1)+1!=(r1-l1+1)){
        ll cur=query(1,0,n-1,l1,r1);
        r1++;
      }
      for (ll i = 0; i <= r1; ++i)
      {
        ans.insert(ari[i]);
      }
    }
  }
  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:86:8: warning: unused variable 'cur' [-Wunused-variable]
     ll cur=query(1,0,n-1,l,r);
        ^~~
tenis.cpp:124:12: warning: unused variable 'cur' [-Wunused-variable]
         ll cur=query(1,0,n-1,l1,r1);
            ^~~
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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 2 ms 3456 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Correct 2 ms 3456 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 2 ms 3456 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Correct 2 ms 3456 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 3 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 4 ms 3456 KB Output is correct
12 Correct 4 ms 3456 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 2 ms 3456 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Correct 2 ms 3456 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 3 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 4 ms 3456 KB Output is correct
12 Correct 4 ms 3456 KB Output is correct
13 Execution timed out 520 ms 9336 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 8060 KB Output is correct
2 Correct 441 ms 6136 KB Output is correct
3 Correct 405 ms 6136 KB Output is correct
4 Correct 432 ms 5880 KB Output is correct
5 Correct 421 ms 5880 KB Output is correct
6 Correct 417 ms 5920 KB Output is correct
7 Correct 390 ms 5752 KB Output is correct
8 Correct 419 ms 5836 KB Output is correct
9 Correct 416 ms 6072 KB Output is correct
10 Correct 429 ms 5792 KB Output is correct
11 Correct 453 ms 6868 KB Output is correct
12 Correct 397 ms 5896 KB Output is correct
13 Correct 412 ms 6008 KB Output is correct
14 Correct 401 ms 5880 KB Output is correct
15 Correct 407 ms 6064 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 2 ms 3456 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Correct 2 ms 3456 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 3 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 4 ms 3456 KB Output is correct
12 Correct 4 ms 3456 KB Output is correct
13 Execution timed out 520 ms 9336 KB Time limit exceeded
14 Halted 0 ms 0 KB -