Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #pragma GCC target("avx,avx2,fma")
- #include <bits/stdc++.h>
- using namespace std;
- int cnt;
- const int MAX = 2169800;
- const int INF = 1000000000;
- struct segment{
- int val;
- int lazy;
- int koji;
- } seg[4*MAX+5];
- int sta[MAX+5];
- void propagate(int node, int l, int r){
- seg[node].val += seg[node].lazy;
- if(l == r){
- seg[node].lazy = 0;
- return;
- }
- seg[node*2].lazy += seg[node].lazy;
- seg[node*2+1].lazy += seg[node].lazy;
- seg[node].lazy = 0;
- }
- void updatuj(int node, int l, int r){
- seg[node].val = min(seg[node*2].val+seg[node*2].lazy, seg[node*2+1].val+seg[node*2+1].lazy);
- if(seg[node*2].val+seg[node*2].lazy == seg[node].val) seg[node].koji = seg[node*2].koji;
- else seg[node].koji = seg[node*2+1].koji;
- }
- void updseg(int node, int l, int r, int tl, int tr, int val){
- if(l > tr || tl > r) return;
- if(tl <= l && r <= tr){
- seg[node].lazy += val;
- propagate(node, l, r);
- return;
- }
- propagate(node, l, r);
- int mid = (l+r)/2;
- updseg(node*2, l, mid, tl, tr, val);
- updseg(node*2+1, mid+1, r, tl, tr, val);
- updatuj(node, l, r);
- }
- void updpoint(int node, int l, int r, int x, int val){
- if(l == r){
- seg[node].koji = l;
- seg[node].val = val;
- seg[node].lazy = 0;
- return;
- }
- propagate(node, l, r);
- int mid = (l+r)/2;
- if(mid >= x) updpoint(node*2, l, mid, x, val);
- else updpoint(node*2+1, mid+1, r, x, val);
- updatuj(node, l, r);
- }
- void init(int node, int l, int r){
- if(l == r){
- seg[node].koji = seg[node].val = INF;
- return;
- }
- seg[node].koji = seg[node].val = INF;
- int mid = (l+r)/2;
- init(node*2, l, mid);
- init(node*2+1, mid+1, r);
- }
- int getval(int node, int l, int r, int x){
- propagate(node, l, r);
- if(l == r) return seg[node].val;
- int mid = (l+r)/2;
- if(mid >= x) return getval(node*2, l, mid, x);
- return getval(node*2+1, mid+1, r, x);
- }
- /// MOJE
- void solve(){
- int n;
- cin >> n;
- if(n == 1){
- cout << 1 << endl;
- return;
- }
- if(n == 2){
- cout << 2 << endl;
- return;
- }
- int res = 0;
- int vel = n-1;
- res = 1;
- for(int i=1; i<=cnt; i++){
- if(vel == 0)break;
- res++;
- int broj = sta[i];
- int pomvel = (vel + broj - 1) / broj;
- vel -= pomvel;
- if(i == cnt){
- cout << sta[i] << " " << pomvel << " " << vel+pomvel << endl;
- }
- if(pomvel == 1){
- break;
- }
- }
- res += vel;
- cout << res << endl;
- }
- int main(){
- ios_base::sync_with_stdio(false), cin.tie(0);
- int n;
- n = 418*1e5;
- init(1, 1, MAX);
- /// ne zaboravi da dodas 1, 2, 3 u niz
- sta[++cnt] = 2;
- sta[++cnt] = 3;
- int kurac = 2;
- for(int i=5; i<=n; i+=6-kurac){
- updseg(1, 1, MAX, 1, cnt, -1);
- if(seg[1].val+seg[1].lazy){
- sta[++cnt] = i;
- updpoint(1, 1, MAX, cnt, sta[cnt]);
- }
- else{
- int k = seg[1].koji;
- updseg(1, 1, MAX, k+1, cnt, 1);
- updpoint(1, 1, MAX, k, sta[k]);
- }
- kurac = 6-kurac;
- }
- //cout << cnt+3 << endl;
- int t;
- cin >> t;
- while(t--)solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement