oj.uz

답안 #535199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535199 2022-03-09T16:41:16 Z NaimSS 케이크 (CEOI14_cake) C++14
0 / 100
 326 ms 17608 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
  return ans;
}

// debug:
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
  cerr << ' ' << H; 
  dbg_out(T...); 
}
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...) 42
#endif
//

const int N = 500100;
int val[N];
char op[N];
int id[N],e[N],b[N];
vi top10;
int num[N],ini[N];
int nxt[N];
int last[N];

// seg:
int tree[4*N];
void upd(int no,int i,int j,int p,int v){
  if(i==j){
    tree[no] = v;
    return;
  }
  int m = (i+j)/2,l=2*no,r=2*no+1;
  if(p<=m)upd(l,i,m,p,v);
  else upd(r,m+1,j,p,v);
  tree[no] = max(tree[l],tree[r]);
}
int query(int no,int i,int j,int a,int b){
  if(i>j || i > b || j < a)return 0;
  if(a<=i && j<=b)return tree[no];
  int m = (i+j)/2,l=2*no,r=2*no+1;
  return max(query(l,i,m,a,b),query(r,m+1,j,a,b));
}
int buscaL(int no,int i,int j,int idr,int mx){
  if(i > idr)return 0;
  if(tree[no] < mx)return 0;
  if(i==j)return i;
  int m = (i+j)/2,l=2*no,r=2*no+1;
  int op1 = buscaL(r,m+1,j,idr,mx);
  if(op1!=0)return op1;
  return buscaL(l,i,m,idr,mx);
}
    int n,a;

int buscaR(int no,int i,int j,int idl,int mx){
  if(j < idl)return n+1;
  if(tree[no] < mx)return n+1;
  if(i==j)return i;
  int m = (i+j)/2,l=2*no,r=2*no+1;
  int op1 = buscaR(l,i,m,idl,mx);
  if(op1!=n+1)return op1;
  return buscaR(r,m+1,j,idl,mx);
}

int32_t main(){
    fastio;
    cin >> n >> a;
    for(int i=1;i<=n;i++){
      cin >> val[i];
      ini[i] = val[i];
      if(val[i] >= n-9)top10.pb(i);
    }
    int q;
    cin >> q;
    int mx = n;
    for(int i=1;i<=q;i++){
      cin >> op[i];
      if(op[i] == 'E'){
        cin >> id[i] >> e[i];
        sort(all(top10),[&](int i1,int i2){
          return  val[i1] > val[i2];
        });

        if(sz(top10) > min(n,10))top10.pop_back();
        mx += e[i];
        for(int j=0;j<e[i]-1;j++){
          
          val[top10[j]] = mx - j;
          
          if(last[top10[j]]>0)
            nxt[last[top10[j]]] = val[top10[j]];
          else
            ini[top10[j]] = val[top10[j]];
        }
        if(num[id[i]] == 0){
          ini[id[i]] = val[id[i]];
          num[id[i]]=1;
        }

        nxt[i] = mx - e[i] + 1;
        val[id[i]] = nxt[i];
        last[id[i]] = i;

        dbg(id[i],nxt[i]);

        int dentro=0;
        for(auto it : top10)if(it == id[i])dentro=1;
        if(!dentro)
          top10.pb(id[i]);
      }else{
        cin >> b[i];
      }
    }
    

    rep(i,1,n+1){
      upd(1,1,n,i,ini[i]);
      dbg(ini[i]);
    }

    rep(i,1,q+1)if(op[i]=='E'){
      dbg(id[i],nxt[i]);
      upd(1,1,n,id[i],nxt[i]);
    }else{
      if(b[i] == a){
        cout << 0 << endl;
      }else if(b[i] > a){
        int mx = query(1,1,n,a+1,b[i]);
        int l = (a == 1 ? 0 : buscaL(1,1,n,a-1,mx)) + 1;
        dbg(b[i],mx,l);
        cout << b[i]-l << endl;
      }else{
        int mx = query(1,1,n,b[i],a-1);
        int r = (a==n ? n + 1 : buscaR(1,1,n,a+1,mx)) - 1;
        dbg(b[i],mx,r);
        cout << r - b[i] << endl;
      }
    }
    // math -> gcd it all
    // Did u check N=1? Did you switch N,M?
}

Compilation message

cake.cpp: In function 'int32_t main()':
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:141:9: note: in expansion of macro 'dbg'
  141 |         dbg(id[i],nxt[i]);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:155:7: note: in expansion of macro 'dbg'
  155 |       dbg(ini[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:159:7: note: in expansion of macro 'dbg'
  159 |       dbg(id[i],nxt[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:167:9: note: in expansion of macro 'dbg'
  167 |         dbg(b[i],mx,l);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:172:9: note: in expansion of macro 'dbg'
  172 |         dbg(b[i],mx,r);
      |         ^~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 9268 KB Output isn't correct
2 Correct 126 ms 8024 KB Output is correct
3 Correct 144 ms 9420 KB Output is correct
4 Correct 125 ms 8252 KB Output is correct
5 Incorrect 158 ms 8480 KB Output isn't correct
6 Incorrect 150 ms 8448 KB Output isn't correct
7 Correct 155 ms 8516 KB Output is correct
8 Correct 128 ms 8640 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 4612 KB Output is correct
2 Incorrect 59 ms 4120 KB Output isn't correct
3 Correct 53 ms 3848 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 103 ms 6580 KB Output is correct
6 Incorrect 95 ms 6608 KB Output isn't correct
7 Correct 86 ms 6084 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 1460 KB Output isn't correct
2 Correct 22 ms 1496 KB Output is correct
3 Correct 43 ms 3228 KB Output is correct
4 Incorrect 42 ms 3260 KB Output isn't correct
5 Incorrect 52 ms 3276 KB Output isn't correct
6 Correct 77 ms 4884 KB Output is correct
7 Correct 73 ms 4548 KB Output is correct
8 Correct 85 ms 6340 KB Output is correct
9 Correct 326 ms 17608 KB Output is correct
10 Incorrect 184 ms 11076 KB Output isn't correct
11 Incorrect 207 ms 12100 KB Output isn't correct
12 Correct 279 ms 15608 KB Output is correct
13 Incorrect 276 ms 16576 KB Output isn't correct