| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MSE06H - Japan |
| English | Vietnamese |
Japan chuẩn bị chào đón ACM ICPC World Finals và muốn xây 1 số đường. Japan là 1 hòn đảo với N thành phố ở bờ phía Đông và M thành phần ở bờ phía Tây, (M ≤ 1000, N ≤ 1000). Các thành phố ở mỗi bờ được đánh số từ 1 trở đi theo chiều từ Bắc tới Nam. K superhighways sẽ được xây để nối bờ phía Đông và bờ phía Tây của Japan. Mỗi superhighway là 1 đường thẳng nối 1 thành phố ở bờ Đông và 1 thành phố ở bờ Tây.
Xác định số giao điểm của các đường cao tốc này. Không có 3 đường cao tốc cắt nhau tại 1 điểm.
Dòng đầu của file Input là T - số test. Mỗi test bắt đầu bởi 3 số – N, M, K. Tiếp theo là K dòng, mỗi dòng 2 số mô tả cặp thành phố được nối bởi đường cao tốc (số thứ nhất ở bờ Đông, số thứ hai ở bờ Tây)
Với mỗi test case, in ra 1 dòng có dạng :
Test case "case number": "số giao điểm"
Chu y : khong co dau cach nao giua "case number" va dau ":" dau nhe, ko thi ban se ko hieu tai sao ko AC.Sample
Input : 1 3 4 4 1 4 2 3 3 2 3 1 Ouput: Test case 1: 5
| Được gửi lên bởi: | psetter |
| Ngày: | 2009-04-16 |
| Thời gian chạy: | 0.209s-1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
| Nguồn bài: | Southeastern European 2006 |
hide comments
|
||||||
|
2020-03-27 21:21:52
dùng BIT để giới hạn 10^6 mới AC :v |
||||||
|
2019-08-28 18:29:25
My Solution: https://vn.spoj.com/files/src/24311622/ |
||||||
|
2018-12-21 20:12:27
… kq để long long nha frostpixel aka.How 2 AC |
||||||
|
2018-11-20 08:24:10
share code từ thiện :v https://pastebin.ubuntu.com/p/PYGQWyKKZN/ Ai dùng nhớ để lại cmt cho mình biết nhé <3 Last edit: 2018-11-20 08:25:09 |
||||||
|
2017-06-02 18:37:51
bài này có thể giải bằng pp tính tổng nhanh :)))) |
||||||
|
2017-02-16 18:06:45
ez mà free code cho mấy bạn nhé đang vui #include <bits/stdc++.h> #define forr(i,a,b) for( long i=a ; i<=b ; ++i) #define ll long long #define s second #define f first using namespace std; const long dad=2e6; long n,k,m,test ; long long t[2000],ans ; pair< long,long > a[dad] ; ll get(long u) { ll res=0; while (u>0) { res+=t[u]; u-=u&-u; } return res; } void update(long u) { while (u<=m) { ++t[u]; u+=u&-u; } } void reset() { memset(t,0,sizeof(t)); ans=0ll; } int main() { // cout << "Hello world!" << endl; // freopen( "MSE06H.inp" , "r" , stdin ); scanf("%d",&test); forr(itest,1,test) { reset(); scanf("%d%d%d",&n,&m,&k); forr(i,1,k) scanf("%d%d",&a[i].f,&a[i].s); sort(a+1,a+k+1); forr(i,1,k) { ans+=i-1-get(a[i].s); update(a[i].s); } printf("Test case %d: %lld\n",itest,ans); } return 0; } |
||||||
|
2015-08-10 17:42:23 N�ng D�n John
OK! K<=1000*1000 =))) http://nhatkynghiencuu.blogspot.com/2015/08/japan-ma-mse06h-spoj_10.html |
||||||
|
2015-06-10 10:12:43 Phong
Last edit: 2015-06-10 10:55:50 |
||||||
|
2015-06-02 22:09:49 there's no salvation for me...
qsort+ IT -----> TLE =))) chịu luôn... |
||||||
|
2015-05-11 07:00:41 Prismatic
k<=M*N :v hèn j NZEC hoài |
||||||
RSS