API tools faq
paste
Advertisement
sandro1234

kuana cxenebi

sandro1234
Jun 15th, 2017
97
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.42 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. //#define CHKR
  7. #define ll long long
  8. #define pb push_back
  9. //#define mp make_pair
  10. #define fr first
  11. #define sc second
  12. #define ARRS int(2e5+500)
  13. #define BARRS int(6e4+600)
  14. #define MAX ((long long)(1e9+1))
  15. #define EP ((double)(1e-12))
  16. #define MMAX ((long long)(1e9+10))
  17. #define HS1 ((long long)(1000001329))
  18. #define HS2 ((long long)(1000001531))
  19. #define MOD ((long long)1000000000ll)
  20. #define SQ 31622780
  21. #define PI 3.14159265358979323846264338327950288419716939937510
  22. #define BG 4294967232ll
  23. #define MH 200008
  24.  
  25. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  26.  
  27. ordered_set s;
  28.  
  29.  
  30. pair<ll,ll> a[ARRS];
  31. pair<ll,ll> b[ARRS];
  32. vector<ll> v[ARRS];
  33. ll pr[ARRS];
  34.  
  35.  
  36. ll m;
  37. ll bld(ll x){
  38.     ll c=x+1;
  39.     while(c<m&&a[c].sc<=a[x].sc){
  40.        // cout<<x<<" <> "<<c<<endl;
  41. //        if(a[c].sc>a[x].sc){
  42. //          assert(0);
  43. //          exit(5);
  44. //        }
  45.         v[x].pb(c);
  46.         c=bld(c);
  47.     }
  48.     if(c-1==x){
  49.         for(int i=a[x].fr; i<=a[x].sc; i++)
  50.             pr[i]=x;
  51.     }
  52.     else {
  53.         //cout<<a[x].fr<<" "<<a[x+1].fr<<" "<<
  54.         for(int i=a[x].fr; i<a[x+1].fr; i++)
  55.             pr[i]=x;
  56.         for(int i=a[c-1].sc+1; i<=a[x].sc; i++)
  57.             pr[i]=x;
  58.     }
  59.     return c;
  60. }
  61.  
  62. ll in[ARRS];
  63. ll out[ARRS];
  64. ll dt[ARRS];
  65. vector<pair<ll,ll> > lca;
  66.  
  67.  
  68. void go(ll x,ll d){
  69.     in[x]=lca.size();
  70.     dt[x]=d;
  71.     for(auto y:v[x]){
  72.         lca.pb({d,x});
  73.         go(y,d+1);
  74.     }
  75.     out[x]=lca.size();
  76.     lca.pb({d,x});
  77. }
  78.  
  79. pair<ll,ll> rq[ARRS][23];
  80.  
  81. void blrq(){
  82.     ll n=lca.size();
  83.     for(int i=n-1; i>=0; i--){
  84.         rq[i][0]=lca[i];
  85.         for(int t=0; t<19; t++)
  86.             rq[i][t+1]=min(rq[i][t],rq[min(n-1,0ll+i+(1<<t))][t]);
  87.     }
  88. }
  89. ll lg2[ARRS];
  90.  
  91. ll mamaa(ll l,ll r){
  92.     ll k=lg2[r-l]-1;
  93.     return min(rq[l][k],rq[r+1-(1<<k)][k]).sc;
  94. }
  95.  
  96. ll caaa(ll l,ll r){
  97.     if(l>r)swap(l,r);
  98.     if(l==r)return l;
  99.     if(out[r]<=out[l])return l;
  100.     return mamaa(out[l],in[r]);
  101. }
  102.  
  103. set<ll> ss;
  104.  
  105. #ifndef CHKR
  106. int main(){
  107. #else
  108. int doit(fstream &in,fstream &out){
  109.     cin.rdbuf(in.rdbuf());
  110.     //cout.rdbuf(out.rdbuf());
  111. #endif
  112.     #ifdef KHOKHO
  113.         #ifndef CHKR
  114.         freopen("in.in","r",stdin);
  115.         freopen("out.out","w+",stdout);
  116.         #endif //CHKR
  117.     #endif //KHOKHO
  118.     lg2[0]=0;
  119.     for(int i=1; i<ARRS-10; i++){
  120.         lg2[i]=lg2[i-1];
  121.         if((i&(i-1))==0){lg2[i]++;}
  122.         //cout<<lg2[i]<<endl;
  123.     }
  124.     lg2[0]=0;
  125.    // return 0;
  126.     ll n,R,t;
  127.     cin>>n>>m>>R;
  128.     for(int i=0; i<n-1; i++){
  129.         cin>>t;
  130.         if(t>=R)ss.insert(i);
  131.     }
  132.     s.insert(-1);
  133.     for(int i=0; i<=n; i++){
  134.         s.insert(i);
  135.     }
  136. ll   l,r,sl, q=0;
  137. ll po=0;
  138.     for(int i=0; i<m; i++){
  139.         cin>>l>>r;
  140.         ll t=r-l;
  141.         po+=t;
  142.          l++;
  143.         sl=l;
  144.         r++;
  145.         l=*s.find_by_order(l-1)+1;
  146.         r=*s.find_by_order(r);
  147.         while(t--)s.erase(s.find_by_order(sl));
  148. //      for(auto it=s.begin(); it!=s.end(); it++){
  149. //          cout<<*it<<" ";
  150. //      }
  151.         //cout<<endl;
  152.         a[i]={l,-r};
  153.         //cout<<i<<" "<<l<<" "<<r<<endl;
  154.     }
  155.     cout<<"PO: "<<po<<endl;
  156.     sort(a,a+m);
  157.  
  158.     for(int i=0; i<m; i++){
  159.         a[i].sc*=-1;
  160.     }
  161.    // cout<<endl;
  162.     for(int i=0; i<m; i++){
  163.         cout<<a[i].fr<<" "<<a[i].sc<<endl;
  164.     }
  165.     bld(0);
  166. //    for(int i=0; i<n; i++){
  167. //      cout<<pr[i]<<" ";
  168. //    }
  169. //    cout<<endl;
  170.     go(0,0);
  171.     blrq();
  172. //    for(int i=0; i<lca.size(); i++){
  173. //      cout<<lca[i].fr<<" "<<lca[i].sc<<" / ";
  174. //    }
  175. //    cout<<endl;
  176. //  cout<<endl;
  177. //  cout<<endl;
  178. //  cout<<caaa(1,3)<<endl;
  179. //  cout<<endl;
  180.     ///return 0;
  181.     pair<ll,ll> pas={0,0};
  182.     for(int i=0; i<n; i++){
  183.         ll t;
  184.         auto it=ss.lower_bound(i);
  185.         ll k=MAX;
  186. //        for(auto it:ss){
  187. //          if((it)>=i){
  188. //              t=caaa(pr[(it)+1],pr[i]);
  189. //          } else {
  190. //              t=caaa(pr[it],pr[i]);
  191. //          }
  192. //          cout<<i<<" "<<it<<" "<<t<<" "<<dt[t]<<" "<<dt[pr[i]]<<" "<<dt[pr[i]]-dt[t]<<endl;
  193. //          k=min(k,dt[pr[i]]-dt[t]);
  194. //      }
  195.  
  196.  
  197.         if(it!=ss.end()){
  198.             t=caaa(pr[(*it)+1],pr[i]);
  199.             cout<<(*it)+1<<" "<<dt[pr[i]]<<" = "<<dt[t]<<endl;
  200.             k=min(k,dt[pr[i]]-dt[t]);
  201.             //pas=max(pas,);
  202.         }
  203.         if(it!=ss.begin()){
  204.             it--;
  205.             cout<<(*it)<<" "<<pr[i]<<" = "<<caaa(pr[*it],pr[i])<<endl;
  206.             t=caaa(pr[*it],pr[i]);
  207.             k=min(k,dt[pr[i]]-dt[t]);
  208.         }
  209.         cout<<i<<" "<<k<<endl;
  210.         pas=max(pas,{k,-i});
  211.     }
  212.     cout<<-pas.sc;
  213.     return 0;
  214. }
  215.  
  216. //
  217. //
  218. //#include<bits/stdc++.h>
  219. //using namespace std;
  220. //int a,s,d[100002],d1[100002][2],f,g,h,j,k,l,i,n,m,ans,pos;
  221. //vector<int> v1[200002];
  222. //
  223. //int pr1[19][200003],pas[200003],lv1[200002];
  224. //struct tre{
  225. //    int val;
  226. //    int shep;
  227. //    tre *L;
  228. //    tre *R;
  229. //    tre(){
  230. //        val=0;
  231. //        shep=-1;
  232. //        L=NULL;
  233. //        R=NULL;
  234. //    }
  235. //};
  236. //
  237. //void shd(tre *&it,int rd){
  238. //    if(rd==1) {it->shep=-1;return;}
  239. //    if(!it->L) it->L=new tre();
  240. //    if(!it->R) it->R=new tre();
  241. //    it->L->shep=it->shep;
  242. //    it->R->shep=it->shep;
  243. //    it->L->val=rd/2*it->shep;
  244. //    it->R->val=(rd-rd/2)*it->shep;
  245. //    it->shep=-1;
  246. //    return;
  247. //}
  248. //
  249. //void add(tre *&it,int l,int r,int lf,int rg,int val){
  250. //    if(l>=rg || r<=lf) return;
  251. //    if(!it) it=new tre();
  252. //    if(l>=lf && r<=rg) {
  253. //        it->shep=val;
  254. //        it->val=(r-l)*val;
  255. //        return;
  256. //    }
  257. //    if(it->shep!=-1) shd(it,r-l);
  258. //    add(it->L,l,(l+r)/2,lf,rg,val);
  259. //    add(it->R,(l+r)/2,r,lf,rg,val);
  260. //    it->val=(it->L ? it->L->val : 0)+(it->R ? it->R->val : 0);
  261. //    //cout<<">>"<<l<<" "<<r<<" "<<it->val<<endl;
  262. //}
  263. //
  264. //int fnd(tre *&it,int l,int r,int val){//cout<<l<<" "<<r<<" "<<val<<" :"<<it->val<<endl;
  265. //    if(it->shep!=-1) return l+val-1;
  266. //    if(l+1==r) return l;
  267. //    int y=it->L ? it->L->val : 0;
  268. //    if(y>=val) return fnd(it->L,l,(l+r)/2,val);
  269. //    else return fnd(it->R,(l+r)/2,r,val-y);
  270. //}
  271. //tre *lf;
  272. //
  273. //////////////////////////////////////////
  274. //
  275. //
  276. //void upd(int l,int r,int pr){
  277. //    for(int i=l;i<r;i=d1[i][1]){//cout<<i;
  278. //        //cout<<" "<<d1[i][0]<<" "<<pr<<endl;
  279. //        v1[pr].push_back(d1[i][0]);
  280. //    }
  281. //}
  282. //
  283. //void df1(int idx,int lv){
  284. //    lv1[idx]=lv;
  285. //    for(auto it:v1[idx]){
  286. //        pr1[0][it]=idx;
  287. //        df1(it,lv+1);
  288. //    }
  289. //}
  290. //
  291. //
  292. //int lca(int i1,int i2){//cout<<i1<<" "<<i2<<endl;
  293. //    int i,ret=lv1[i1];
  294. //    if(lv1[i1]<lv1[i2]) {swap(i1,i2);}
  295. //    i=18;
  296. //    while(lv1[i1]>lv1[i2]){
  297. //        for(;i>=0;i--){
  298. //            if(pr1[i][i1]!=-1 && lv1[pr1[i][i1]]>=lv1[i2]) {i1=pr1[i][i1];break;}
  299. //        }//cout<<i1<<" "<<i2<<endl;
  300. //        if(!i) break;
  301. //    }//cout<<endl;
  302. //
  303. //    while(i1!=i2){
  304. //        for(;i>0;i--){
  305. //            if(pr1[i][i1]!=pr1[i][i2]) break;
  306. //        }//cout<<i<<"&";
  307. //        i1=pr1[i][i1];
  308. //        i2=pr1[i][i2];
  309. //    }//cout<<i1<<" "<<ret<<endl<<endl;
  310. //    return ret-lv1[i1];
  311. //}
  312. //
  313. //int main(){
  314. //
  315. //  #ifdef KHOKHO
  316. //        #ifndef CHKR
  317. //        freopen("in.in","r",stdin);
  318. //        freopen("out.out","w+",stdout);
  319. //        #endif //CHKR
  320. //    #endif //KHOKHO
  321. //    //lv1[0]=-1;
  322. //    memset(pr1,~0,sizeof pr1);
  323. //    cin>>n>>m>>k;
  324. //    d1[0][1]=1;
  325. //    for(i=0;i<n-1;i++){
  326. //        scanf("%d",&d[i]);
  327. //        d1[i+1][0]=i+1;
  328. //        d1[i+1][1]=i+2;
  329. //    }
  330. //    h=n;j=n;
  331. //    add(lf,0,n,0,n,1);
  332. //  vector<pair<int,int> > va;
  333. //    for(i=0;i<m;i++){
  334. //        scanf("%d%d",&a,&s);
  335. //        a++;s++;
  336. //        f=fnd(lf,0,n,a);
  337. //        g=fnd(lf,0,n,s);
  338. //        //cout<<f<<" "<<g<<endl;
  339. //        va.push_back({f,-g});
  340. //        add(lf,0,n,f+1,g+1,0);
  341. //        //cout<<"*"<<f<<" "<<g<<endl;
  342. //
  343. //        upd(f,g+1,h);
  344. //        d1[f][0]=h;
  345. //        h++;
  346. //        d1[f][1]=d1[g][1];
  347. //    }
  348. //    sort(va.begin(),va.end());
  349. //    for(auto t:va){
  350. //      cout<<t.first<<" "<<-t.second<<endl;
  351. //    }
  352. //
  353. //    df1(h-1,0);
  354. //
  355. //
  356. //    for(i=1;i<18;i++){
  357. //        for(a=0;a<h;a++){
  358. //            if(pr1[i-1][a]==-1) continue;
  359. //
  360. //            pr1[i][a]=pr1[i-1][pr1[i-1][a]];
  361. //        }
  362. //    }
  363. //    f=h-1;
  364. //    for(i=0;i<n;i++){
  365. //        pas[i]=lca(i,f);
  366. //        //cout<<lv1[i]<<endl;
  367. //        if(d[i]>k) f=i;
  368. //    }
  369. //    f=j-1;
  370. //    for(i=n-1;i>=0;i--){
  371. //        g=lca(i,f+1);
  372. //        //cout<<pas[i]<<"| "<<g<<endl;
  373. //        pas[i]=min(pas[i],g);
  374. //        if(ans<=pas[i]){ans=pas[i];pos=i;}
  375. //        if(d[i-1]>k) f=i-1;
  376. //    }
  377. //    if(k!=n-1) ans--;
  378. //    cout<<pos;
  379. //}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!