Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
1408K 329ms 过了 附个代妈 错误真弱智,排序的时猴忘记把C值也交换了。。。In Reply To:线段树,估计是数组越界了,竟然报TLE,下了官方数据本地跑各种RE,还在debug。。。 Posted by:KatrineYang at 2016-09-03 02:41:08 #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; int val[240000] = {0}; int n; int prev[50005]; bool has[50005] = {0}; struct intv{ int start, end, c; } intvs[50005]; bool compare(const intv &i1, const intv &i2){ return i1.end < i2.end; } int query(int start, int end, int qstart, int qend, int bh){ if(qstart == start && qend == end) return val[bh]; int qmid = (qstart + qend)/2; if(end <= qmid) return query(start, end, qstart, qmid, 2*bh+1); else if(start > qmid) return query(start, end, qmid+1, qend, 2*bh+2); else return query(start, qmid, qstart, qmid, 2*bh+1) + query(qmid+1, end, qmid+1, qend, 2*bh+2); } void add(int place, int start, int end, int bh){ val[bh]++; if(start == end){ return; } int mid = (start + end)/2; if(place <= mid){ add(place, start, mid, 2*bh+1); } else{ add(place, mid+1, end, 2*bh+2); } } int main() { scanf("%d", &n); //cout << n_ << endl; int mx = 0; for(int i = 0; i < n; i++){ scanf("%d%d%d", &intvs[i].start, &intvs[i].end, &intvs[i].c); if(intvs[i].end > mx) mx = intvs[i].end; } int n_ = 65535; sort(intvs, intvs+n, compare); //cout << intvs[0].start << " " << intvs[0].end << endl; for(int i = 0; i <= n; i++) prev[i] = i-1; for(int i = 0; i < n; i++){ //cout << i << endl; int yygs = query(intvs[i].start, intvs[i].end, 0, n_, 0); if(yygs >= intvs[i].c) continue; int cha = intvs[i].c - yygs; int ks = intvs[i].end; //cout << cha << endl; while(cha > 0){ //cout << cha << endl; while(ks >= 0 && has[ks]){ ks = prev[ks]; } if(ks >= intvs[i].start){ add(ks, 0, n_, 0); cha--; has[ks] = 1; ks--; } } while(ks >= 0 && has[ks]){ ks = prev[ks]; } prev[intvs[i].end] = ks; } printf("%d\n", val[0]); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator