Submission #42750

#	Time	Username	Problem	Language	Result	Execution time	Memory
42750		yusufake	Ancient Books (IOI17_books)	C++98	70 / 100	2061 ms	161440 KiB

books

#include<bits/stdc++.h>
 
using namespace std;
 
#define _   int v, int tl, int tr, int l, int r
#define tm  (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;
typedef pair < ll , ll > pp;
 
const int mod = 1e9 + 7;
const int N   = 1e6 + 6;

set < int > W[N];

int H[N],T[N],n,i,j,l,r,t,a,b,mn,mx,u,h;
int smn[N<<2],smx[N<<2];
ll x;

void up(int p) {  // set value at position p
  for (smn[p += n] = a, smx[p] = b; p > 1; p >>= 1){
      smn[p>>1] = min(smn[p] , smn[p^1]);
      smx[p>>1] = max(smx[p] , smx[p^1]);
  }
}

void qry(int l, int r) {  // sum on interval [l, r)
    r++;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) { mn = min(mn , smn[l]); mx = max(mx , smx[l]);  l++; }
    if (r&1) { r--; mn = min(mn , smn[r]); mx = max(mx , smx[r]);  }
  }
}

ll minimum_walk(vector < int > p, int s){
    x = 0;
    n = p.size();
   // if(n > 1000) return 0;
    memset(smn , 22 , sizeof smn);
	for(i=0;i<n;i++){
		x += abs(p[i] - i);
		if(H[i]) continue;
		r = i;
		for(j=i; !H[j] ; j = p[j]){
			H[j] = 1;
			r = max(r , j);
		}
        for(j=i; !T[j] ; j = p[j]){
		    T[j] = 1;
            a = i;  b = r;
            up(j);
        }
    }
    
    for(i=0;i<n && p[i] == i; i++);
    for(j=n-1;j>=0 && p[j] == j; j--);
 
    queue < pair < int , pp > > Q[2];
    Q[h=0].push(mp(0,mp(s,s)));
    for(;;){
        if(Q[h].size() == 0) h = !h;
        l = Q[h].front().nd.st;
        r = Q[h].front().nd.nd;
        u = Q[h].front().st;
        Q[h].pop();
        if(W[l].find(r) != W[l].end()) continue;
      //  cout << l << " " << r << " " << -u << " aa\n";
        if(l <= i && r >= j) return x + -u-u;
        W[l].insert(r);
        mn = n; mx = 0;
        qry(l,r);
        Q[h].push(mp(u,mp(mn,mx)));
        if(l) Q[!h].push(mp(u-1,mp(l-1,r)));
        if(r < n-1) Q[!h].push(mp(u-1,mp(l,r+1)));
    }
}	
 /*
int main(){
    cout << minimum_walk({1,0,2,3} , 2);
}*/

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30