1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 20400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 int sum[mnx<<2], h, w, n;;19 void pushup( int rt ){20     sum[rt] = max( sum[rt<<1], sum[rt<<1|1] );21 }22 void build( int l, int r, int rt ){23     if( l == r ){24         sum[rt] = w; return ;25     }26     int m = ( l + r ) >> 1;27     build( lson );28     build( rson );29     pushup( rt );30 }31 int find( int v, int l, int r, int rt ){32     int ret;33     if( l == r ){34         if( sum[rt] < v ) ret = -1;35         else sum[rt] -= v, ret = l;36         return ret;37     }38     int m = ( l + r ) >> 1;39     if( sum[rt<<1] >= v ){40         ret = find( v, lson );41     }42     else  ret = find( v, rson );43     pushup( rt );44     return ret;45 }46 int main(){47     while( scanf( "%d %d %d", &h, &w, &n ) != EOF ){48         h = min( h, n );49         build( 1, h, 1 );50         int ww;51         for( int i = 0; i < n; i++ ){52             scanf( "%d", &ww );53             printf( "%d\n", find( ww, 1, h, 1 ) );54         }55     }56     return 0;57 }

 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 20400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 int sum[mnx<<2], pos[mnx], val[mnx], ans[mnx], n;19 void pushup( int rt ){20     sum[rt] = sum[rt<<1] + sum[rt<<1|1];21 }22 void build( int l, int r, int rt ){23     if( l == r ){24         sum[rt] = 1; return ;25     }26     int m = ( l + r ) >> 1;27     build( lson );28     build( rson );29     pushup( rt );30 }31 void update( int p, int v, int l, int r, int rt ){32     if( l == r ){33         sum[rt] = 0;34         ans[l] = v;35         return ;36     }37     int m = ( l + r ) >> 1;38     if( p <= sum[rt<<1] ) update( p, v, lson );39     else update( p - sum[rt<<1], v, rson );40     pushup( rt );41 }42 int main(){43     while( scanf( "%d", &n ) != EOF ){44         for( int i = 0; i < n; i++ ){45             scanf( "%d %d", &pos[i], &val[i] );46         }47         build( 1, n, 1 );48         for( int i = n - 1; i >= 0; i-- ){49             update( pos[i]+1, val[i], 1, n, 1 );50         }51         for( int i = 1; i <= n; i++ ){52             printf( "%d%c", ans[i], i == n ? ‘\n‘ : ‘ ‘ );53         }54     }55     return 0;56 }

 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 50400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 int sum[mnx<<2], n, val[mnx], cnt, best, ans;19 char ch[mnx][11];20 int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};21 void pushup( int rt ){22     sum[rt] = sum[rt<<1] + sum[rt<<1|1];23 }24 void build( int l, int r, int rt ){25     if( l == r ){26         sum[rt] = 1;27         return ;28     }29     int m = ( l + r ) >> 1;30     build( lson );31     build( rson );32     pushup( rt );33 }34 int update( int p, int l, int r, int rt ){35     int ret;36     if( l == r ){37         sum[rt] = 0;38         return l;39     }40     int m = ( l + r ) >> 1;41     if( sum[rt<<1] >= p ) ret = update( p, lson );42     else ret = update( p - sum[rt<<1], rson );43     pushup( rt );44     return ret;45 }46 void dfs( int dept, int tmp, int num ){47     if( dept >= 16 ) return;48     if( num > best ){49         best = num;50         ans = tmp;51     }52     if( num == best && ans > tmp ) ans = tmp;53     for( int i = 1; i <= 20; i++ ){54         if( n / p[dept] < tmp ) break;55         dfs( dept + 1, tmp *= p[dept], num * ( i + 1 ) );56     }57 }58 int main(){59     int k;60     while( scanf( "%d %d", &n, &k ) != EOF ){61         ans = inf;62         best = 0;63         dfs( 0, 1, 1 );64         build( 1, n, 1 );65         cnt = 1;66         for( int i = 1; i <= n; i++ ){67             scanf( "%s %d", &ch[i], &val[i] );68         }69         int mod, pre;70         for( int i = 0; i < ans; i++ ){71             pre = k;72             k = update( k, 1, n, 1 );73             if( i == ans-1 ) break;74             mod = sum[1];75             if( val[k] > 0 ){76                 k = ( pre - 1 + val[k] % mod ) % mod;77                 if( k == 0 ) k = mod;78             }79             else{80                 k = ( mod + pre - ( -val[k] % mod ) ) % mod ;81                 if( k == 0 ) k = mod;82             } 83         }84         printf( "%s %d\n", ch[k], best );85     }86     return 0;87 }