Submission #42748

#	Time	Username	Problem	Language	Result	Execution time	Memory
42748		yusufake	고대 책들 (IOI17_books)	C++98	70 / 100	2055 ms	240956 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(_){
   if(tl > r || tr < l) return;
   if(tl >= l && tr <= r) { smn[v] = min(smn[v] , a); smx[v] = max(smx[v] , b); return; }
   up(sol); up(sag); smn[v] = min(smn[v+v] , smn[v+v+1]);
   smx[v] = max(smx[v+v] , smx[v+v+1]);
}
void qry(_){
   if(tl > r || tr < l) return;
   if(tl >= l && tr <= r) { mn = min(mn,smn[v]); mx=max(mx,smx[v]); return; }
   qry(sol); qry(sag);
}
 
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(1,0,n,j,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(1,0,n,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);
}*/

Compilation message (stderr)

books.cpp: In function 'void up(int, int, int, int, int)':
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^
books.cpp:30:7: note: in expansion of macro 'sol'
    up(sol); up(sag); smn[v] = min(smn[v+v] , smn[v+v+1]);
       ^
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^
books.cpp:30:16: note: in expansion of macro 'sag'
    up(sol); up(sag); smn[v] = min(smn[v+v] , smn[v+v+1]);
                ^
books.cpp: In function 'void qry(int, int, int, int, int)':
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^
books.cpp:36:8: note: in expansion of macro 'sol'
    qry(sol); qry(sag);
        ^
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^
books.cpp:36:18: note: in expansion of macro 'sag'
    qry(sol); qry(sag);
                  ^

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