در سریع تر شدن این کد کمک کنید..

[404]

مگه  عملیات insert  و erase توی یک multiset از O(lgn) نیست؟؟
حالا سوال پیش می آد: اینجا ما داریم از O(mlgm)  عملیات انجام می دیم. این کد رو یه نگاهی بزنید:

کد: [انتخاب]

int main(){
cin>>n>>m;
show(n);show(m);
for(int i=0;i<n;i++)
scanf("%d%d",&c[i].a,&c[i].b);
sort(c,c+n);
for(int i=0;i<m;i++)
scanf("%d%d",&t[i].a,&t[i].b);
sort(t,t+m);
int j=0;
for(int i=0;i<n;i++){
while(t[j].b>=c[i].b && j<m){
g.insert(t[j].a);
j++;
}
it tmp=lower_bound(g.begin(),g.end(),c[i].a);
if(tmp== g.end()){
cout<<-1<<endl;
return 0;;
}
ans+=*tmp;
g.erase(tmp);
}
cout<<ans<<endl;
return 0;
}
اما به شیوه فجیعی طول می کشه! راهی برای تند تر شدنش دارید؟!!بد نیست یه نگاهی به این تایم ها برای n و m  ها بندازید:

کد: [انتخاب]

test case # 1 ...
n=4
m=7

real    0m0.002s
user    0m0.000s
sys     0m0.000s
:D
test case # 2 ...
n=10
m=30

real    0m0.002s
user    0m0.004s
sys     0m0.000s
:D
test case # 3 ...
n=40
m=100

real    0m0.002s
user    0m0.000s
sys     0m0.004s
:D
test case # 4 ...
n=1000
m=3000

real    0m0.094s
user    0m0.080s
sys     0m0.004s
:D
test case # 5 ...
n=2000
m=5000

real    0m0.337s
user    0m0.240s
sys     0m0.000s
:D
test case # 6 ...
n=5000
m=5000

real    0m0.535s
user    0m0.428s
sys     0m0.000s
:D
test case # 7 ...
n=10000
m=10000

real    0m2.132s
user    0m1.856s
sys     0m0.000s
:D
test case # 8 ...
n=20000
m=40000

real    0m25.365s
user    0m20.905s
sys     0m0.044s
:D
test case # 9 ...
n=60000
m=100000

real    6m58.769s
user    4m55.470s
sys     0m0.620s
:D
test case # 10 ...
n=100000
m=100000


آگه data structure ه دیگه ای سراغ دارید که در عمل کمتر طول می کشه یا راهنمایی چیزی ، ممنون می شم بگید
آخری رو حال نداشتم واستم تا جواب بده

[ابراهیم]

سلام،
به‌تر هست صورت مسأله رو بگی تا معلوم شه چه جور ساختمان داده‌ای لازم داری.

[404]

خب صورت مسله اینو می خواد:
یه طور data structure که بتونه عملیات insert و delete و lower_bound داشته باشه.
مسله اینجاس Ú©Ù‡ MAXN=10^5 هست Ùˆ تایم لیمیت هم Û± ثانیه. به نظر O(mlgm) مرتبه ÛŒ مناسبی Ù…ÛŒ آد اما اینکه تایم ها Ú©Ù‡ این طور نشون نمی ده 
در هر حال صورت سوال اینه:

**********************************************************************

Problem 2: Gourmet Grazers [Alex Schwendner, 2007]

Like so many others, the cows have developed very haughty tastes
and will no longer graze on just any grass. Instead, Farmer John
must purchase gourmet organic grass at the Green Grass Grocers store
for each of his N (1 <= N <= 100,000) cows.

Each cow_i demands grass of price at least A_i (1 <= A_i <=
1,000,000,000) and with a greenness score at least B_i (1 <= B_i
<= 1,000,000,000). The GGG store has M (1 <= M <= 100,000) different
types of grass available, each with a price C_i (1 <= C_i <=
1,000,000,000) and a greenness score of D_i (1 <= D_i <= 1,000,000,000).
Of course, no cow would sacrifice her individuality, so no two cows
can have the same kind of grass.

Help Farmer John satisfy the cows' expensive gourmet tastes while
spending as little money as is necessary.

PROBLEM NAME: gourmet

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M.

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i
        and B_i

* Lines N+2..N+M+1: Line i+N+1 contains two space-separated integers:
        C_i and D_i

SAMPLE INPUT (file gourmet.in):

4 7
1 1
2 3
1 4
4 2
3 2
2 1
4 3
5 2
5 4
2 6
4 4


OUTPUT FORMAT:

* Line 1: A single integer which is the minimum cost to satisfy all
        the cows. If that is not possible, output -1.

SAMPLE OUTPUT (file gourmet.out):

12

OUTPUT DETAILS:

Cow 1 eats grass 2 at cost 2, cow 2 eats grass 3 at cost 4, cow 3 eats
grass 6 at cost 2, and cow 4 eats grass 7 at cost 4, for a total cost of 12.

*********************************************************************

*


سایتش گاهی گیر Ù…ÛŒ ده باز نمی شه،سوالشو  گذاشتمش همین جا..

[ابراهیم]

سؤال‌های USACO رو باید تنهایی حل کرد!

[404]

سوال به نظر من کاملا حل شده است. کار یه الگوریتم greedy هست و یه data structure ه خوب که کارایی که من می خوام رو بکنه. به نظر می آد mlogm عملیات چیز خوبی باشه ولی من که با stl تازه کارم می خواستم ببینم چیز خوبی می شه توش پیدا کرد یا نه..
 مثه اینکه یکی ندونه sort چیه و خودش رو بزنه و دستی بنویسه ، در حالی که می شده به راحتی از sort stl استفاده کنه. که می شه گفت o(1) سورت می کنه!!! برای این سوال بدیهیه که راه حلی از  O(n) مد نظر نیست،‌وگر نه محدودیت رو نمی داد ۱۰^5 . خوب وقتی مثلا یکی می ره sgu می زنه (اگه می شناسید) و به خاطر اینکه جای cin scanf نذاشته سوال رو تایم می شه،‌فکر می کنم وتقعا نامردی باشه که بهش گفته نشه مشکلت از اینه نه از الگوریتمت که روش مخ زدی! در حال دنبال دیتا ستراکچری از اس تی ال بودم که خب اگه یافت نشد می رم دستی بایری سرچ تری می نویسم! من الگوریتمی برای حل سوال نخواستم تا جایی که یادمه...

[شایان]

به نظر من این کد میتونه از اردر M * n * lg n  باشه البته من دقیقا سوال را نخوندم ولی به نظر میرسه اون for و while تودرتو بتونن در بدترین حالت m * n  بشن.

[404]

اما اون while رو اگه دقت کنید باعث می شه که j حد اکثر یه دور یه ارایه به طول m رو طی کنه. که با insert کردن دیگه می شه mlogm مسئله باید بیش تر با lower_bound و erase باشه. که اونا هم حساب می شه o(lgm) . پس اون قسمت تو در تو باید nlogm+mlogm بشه که چون m>=n هست و n هم از O(m) هست می شه گفت کلا mlgm هست.چون اون قسمت سورت ها هم تو همین اوردر هستن.جایی اشتباهی وجود داره؟

[شایان]

اما اون while رو اگه دقت کنید باعث می شه که j حد اکثر یه دور یه ارایه به طول m رو طی کنه. که با insert کردن دیگه می شه mlogm مسئله باید بیش تر با lower_bound و erase باشه. که اونا هم حساب می شه o(lgm) . پس اون قسمت تو در تو باید nlogm+mlogm بشه که چون m>=n هست و n هم از O(m) هست می شه گفت کلا mlgm هست.چون اون قسمت سورت ها هم تو همین اوردر هستن.جایی اشتباهی وجود داره؟

نه حرف شما کاملا درسته