Language: C++

AIZU ONLINE JUDGE
PAGETOP PROBLEM RANKING STATUS CONTEST COURSE 
 
Logout
 
Register/Setting
Japanese   English
My StatusFor beginners    HOME-
Notes
#2041647 Solution for DSL_4_A: Union of Rectangles by shitoriron
Source Code Status Test Cases     Policy: public     Reviewed: 0    
00.00 sec    3160 KB    96 lines     1858 bytes    2016-10-23 12:37
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
#include<set>
#include<fstream>
using namespace std;
 
const int INF=INT_MAX/3;
typedef unsigned long long ull;
 
struct Rec{
    ull x1, y1, x2, y2;
};
 
ull UnionOfRange(set<int> &now, vector<Rec> &Recs){
    if (now.empty()){return 0;}
 
    ull res = 0;
    int N = Recs.size();
    vector< pair<int, int> > events2;
    int j=0;
    for (set<int>::iterator itra = now.begin();itra!=now.end();itra++){
        events2.push_back(make_pair(Recs[*itra].y1, j) );
        events2.push_back(make_pair(Recs[*itra].y2, j+N) );
        j++;
    }
 
    sort(events2.begin(), events2.end());
 
    int i = 0;
    int prev2 = events2[0].first;
    set<int> now2;
 
    while(i < events2.size()){
        if (!now2.empty()){
            res += ( events2[i].first -prev2 );
        }
        prev2= events2[i].first;
        if(events2[i].second < N){
            now2.insert(events2[i].second);
        }else{
            now2.erase(events2[i].second-N);
        }
        i++;
    }
    return res;
}
 
ull UnionOfRectangle(vector<Rec> &Recs){
    int N = Recs.size();
    vector<pair<int, int> > events;
    for (int i=0;i<N;i++){
        events.push_back(make_pair(Recs[i].x1, i+N));
        events.push_back(make_pair(Recs[i].x2, i));
    }
    sort(events.begin(), events.end());
 
    set<int> now;
    int i= 0;
    int prev = events[0].first;
    ull res = 0;
    while(i<events.size()){
        res += (events[i].first - prev)*UnionOfRange(now, Recs);
        prev = events[i].first;
        while(events[i].first <= prev ){
            if(events[i].second<N){
                now.erase(events[i].second);
            }else{
                now.insert(events[i].second -N);
            }
            i++;
        }
    }
    return res;
}
 
int main(){
    int N;
    cin >> N ;
    vector<Rec> Recs;
    ull x1, y1, x2, y2;
    for (int i =0;i<N;i++){
        cin >> x1 >> y1 >> x2 >> y2 ;
        Rec R ={x1, y1, x2, y2};
        Recs.push_back(R);
    }
    cout << UnionOfRectangle(Recs) <<endl;
    return 0;
}

Compile Error Logs:

Status
Judge: 24/50	C++	CPU: 00.00 sec	Memory: 3160 KB	Length: 1858 B	2016-10-23 12:37	2016-10-23 12:37
Results for testcases
Case #	Verdict	CPU Time	Memory	In	Out	Case Name
Case #1:	: Accepted	00.00 sec	3008 KB	18 B	3 B	sample_1.in
Case #2:	: Accepted	00.00 sec	3140 KB	26 B	2 B	sample_2.in
Case #3:	: Accepted	00.00 sec	3048 KB	34 B	2 B	sample_3.in
Case #4:	: Accepted	00.00 sec	3068 KB	21 B	3 B	sub1_small_in1.in
Case #5:	: Accepted	00.00 sec	3140 KB	24 B	3 B	sub1_small_in2.in
Case #6:	: Accepted	00.00 sec	2996 KB	34 B	3 B	sub1_small_in3.in
Case #7:	: Accepted	00.00 sec	3008 KB	59 B	4 B	sub1_small_in4.in
Case #8:	: Accepted	00.00 sec	3112 KB	39 B	3 B	sub1_small_in5.in
Case #9:	: Accepted	00.00 sec	3080 KB	112 B	4 B	sub1_small_in6.in
Case #10:	: Accepted	00.00 sec	3116 KB	206 B	4 B	sub1_small_in7.in
Case #11:	: Accepted	00.00 sec	3048 KB	32 B	5 B	sub2_easy_in1.in
Case #12:	: Accepted	00.00 sec	3008 KB	26 B	3 B	sub2_easy_in2.in
Case #13:	: Accepted	00.00 sec	3112 KB	43 B	5 B	sub2_easy_in3.in
Case #14:	: Accepted	00.00 sec	3072 KB	73 B	6 B	sub2_easy_in4.in
Case #15:	: Accepted	00.00 sec	3160 KB	139 B	6 B	sub2_easy_in5.in
Case #16:	: Accepted	00.00 sec	3116 KB	275 B	6 B	sub2_easy_in6.in
Case #17:	: Accepted	00.00 sec	3056 KB	687 B	6 B	sub2_easy_in7.in
Case #18:	: Accepted	00.00 sec	3088 KB	1375 B	6 B	sub2_easy_in8.in
Case #19:	: Accepted	00.00 sec	3112 KB	71 B	4 B	sub3_smallrect_in1.in
Case #20:	: Accepted	00.00 sec	3008 KB	138 B	4 B	sub3_smallrect_in2.in
Case #21:	: Accepted	00.00 sec	3152 KB	424 B	4 B	sub3_smallrect_in3.in
Case #22:	: Accepted	00.00 sec	3160 KB	1392 B	5 B	sub3_smallrect_in34.in
Case #23:	: Accepted	00.00 sec	3116 KB	1392 B	5 B	sub3_smallrect_in4.in
Case #24:	: Accepted	00.00 sec	3016 KB	2698 B	5 B	sub3_smallrect_in5.in
Case #25:	: Runtime Error	-	-	44 B	19 B	sub4_corner_in1.in
Case #26:	-	-	-	84 B	19 B	sub4_corner_in2.in
Case #27:	-	-	-	86 B	20 B	sub4_corner_in3.in
Case #28:	-	-	-	53 B	19 B	sub4_corner_in4.in
Case #29:	-	-	-	128 B	20 B	sub4_corner_in5.in
Case #30:	-	-	-	87 B	19 B	sub5_largeeasy_in1.in
Case #31:	-	-	-	83 B	19 B	sub5_largeeasy_in2.in
Case #32:	-	-	-	122 B	19 B	sub5_largeeasy_in3.in
Case #33:	-	-	-	129 B	20 B	sub5_largeeasy_in4.in
Case #34:	-	-	-	419 B	20 B	sub6_largemedium_in1.in
Case #35:	-	-	-	1050 B	20 B	sub6_largemedium_in2.in
Case #36:	-	-	-	2081 B	20 B	sub6_largemedium_in3.in
Case #37:	-	-	-	4163 B	20 B	sub6_largemedium_in4.in
Case #38:	-	-	-	4151 B	20 B	sub6_largemedium_in5.in
Case #39:	-	-	-	4174 B	20 B	sub6_largemedium_in6.in
Case #40:	-	-	-	20803 B	20 B	sub7_largehard_in1.in
Case #41:	-	-	-	41594 B	20 B	sub7_largehard_in2.in
Case #42:	-	-	-	62346 B	20 B	sub7_largehard_in3.in
Case #43:	-	-	-	62301 B	20 B	sub7_largehard_in4.in
Case #44:	-	-	-	83224 B	20 B	sub7_largehard_in5.in
Case #45:	-	-	-	83079 B	20 B	sub7_largehard_in6.in
Case #46:	-	-	-	83104 B	20 B	sub7_largehard_in7.in
Case #47:	-	-	-	92005 B	2 B	sub8_minmax_in1.in
Case #48:	-	-	-	92005 B	20 B	sub8_minmax_in2.in
Case #49:	-	-	-	91997 B	20 B	sub8_minmax_in3.in
Case #50:	-	-	-	91997 B	18 B	sub8_minmax_in4.in

< prev |	25	/	50	| next >	 	sub4_corner_in1.in	 : Runtime Error        -        -
 
Judge Input #25 ( in25.txt | 44 B)		Judge Output #25 ( out25.txt | 19 B)
1
-123456789 -252525252 987654321 525252525
864197529135802470
Comments
 
 Under Construction.
 
Categories
 
 
Free Tags
 
 
 
	  	
 

Aizu Online Judge
follow us on Twitter


About us
ContactSystem InfoThe University of AizuUniv. of Aizu Competitive Programming Club

Tools
WEB Board ToolsVirtual ArenaAPI ReferenceTutorial

Links
ACM/ICPCACM/ICPC Asia JapanACM-ICPC OB/OG Alumni GroupPC KoshienJOI

AtCoderTopCoderCodeForces

Uva Online judgesACM-ICPC Live ArchivePKU JudgeOnline

Aizu IT Arena

Best viewed using Firefox, Google ChromeAizu Online Judge Version 1.0 ?? 2004 - 2016 Univ. of Aizu Competitive Programming Club (ICPCPC), Database Systems Lab. University of Aizu
 

Compiler output:
a.cc:10:10: error: "Solution" is not a valid filename
   10 | #2041647 Solution for DSL_4_A: Union of Rectangles by shitoriron
      |          ^~~~~~~~
a.cc:210:6: error: stray '#' in program
  210 | Case #  Verdict CPU Time        Memory  In      Out     Case Name
      |      ^
a.cc:211:6: error: stray '#' in program
  211 | Case #1:        : Accepted      00.00 sec       3008 KB 18 B    3 B     sample_1.in
      |      ^
a.cc:212:6: error: stray '#' in program
  212 | Case #2:        : Accepted      00.00 sec       3140 KB 26 B    2 B     sample_2.in
      |      ^
a.cc:213:6: error: stray '#' in program
  213 | Case #3:        : Accepted      00.00 sec       3048 KB 34 B    2 B     sample_3.in
      |      ^
a.cc:214:6: error: stray '#' in program
  214 | Case #4:        : Accepted      00.00 sec       3068 KB 21 B    3 B     sub1_small_in1.in
      |      ^
a.cc:215:6: error: stray '#' in program
  215 | Case #5:        : Accepted      00.00 sec       3140 KB 24 B    3 B     sub1_small_in2.in
      |      ^
a.cc:216:6: error: stray '#' in program
  216 | Case #6:        : Accepted      00.00 sec       2996 KB 34 B    3 B     sub1_small_in3.in
      |      ^
a.cc:217:6: error: stray '#' in program
  217 | Case #7:        : Accepted      00.00 sec       3008 KB 59 B    4 B     sub1_small_in4.in
      |      ^
a.cc:218:6: error: stray '#' in program
  218 | Case #8:        : Accepted      00.00 sec       3112 KB 39 B    3 B     sub1_small_in5.in
      |      ^
a.cc:219:6: error: stray '#' in program
  219 | Case #9:        : Accepted      00.00 sec       3080 KB 112 B   4 B     sub1_small_in6.in
      |      ^
a.cc:220:6: error: stray '#' in program
  220 | Case #10:       : Accepted      00.00 sec       3116 KB 206 B   4 B     sub1_small_in7.in
      |      ^
a.cc:221:6: error: stray '#' in program
  221 | Case #11:       : Accepted      00.00 sec       3048 KB 32 B    5 B     sub2_easy_in1.in
      |      ^
a.cc:222:6: error: stray '#' in program
  222 | Case #12:       : Accepted      00.00 sec       3008 KB 26 B    3 B     sub2_easy_in2.in
      |      ^
a.cc:223:6: error: stray '#' in program
  223 | Case #13:       : Accepted      00.00 sec       3112 KB 43 B    5 B     sub2_easy_in3.in
      |      ^
a.cc:224:6: error: stray '#' in program
  224 | Case #14:       : Accepted      00.00 sec       3072 KB 73 B    6 B     sub2_easy_in4.in
      |      ^
a.cc:225:6: error: stray '#' in program
  225 | Case #15:       : Accepted      00.00 sec       3160 KB 139 B   6 B     sub2_easy_in5.in
      |      ^
a.cc:226:6: error: stray '#' in program
  226 | Case #16:       : Accepted      00.00 sec       3116 KB 275 B   6 B     sub2_easy_in6.in
      |      ^
a.cc:227:6: error: stray '#' in program
  227 | Case #17:       : Accepted      00.00 sec       3056 KB 687 B   6 B     sub2_easy_in7.in
      |      ^
a.cc:228:6: error: stray '#' in program
  228 | Case #18:       : Accepted      00.00 sec       3088 KB 1375 B  6 B     sub2_easy_in8.in
      |      ^
a.cc:229:6: error: stray '#' in program
  229 | Case #19:       : Accepted      00.00 sec       3112 KB 71 B    4 B     sub3_smallrect_in1.in
      |      ^
a.cc:230:6: error: stray '#' in program
  230 | Case #20:       : Accepted      00.00 sec       3008 KB 138 B   4 B     sub3_smallrect_in2.in
      |      ^
a.cc:231:6: error: stray '#' in program
  231 | Case #21:       : Accepted      00.00 sec       3152 KB 424 B   4 B     sub3_smallrect_in3.in
      |      ^
a.cc:232:6: error: stray '#' in program
  232 | Case #22:       : Accepted      00.00 sec       3160 KB 1392 B  5 B     sub3_smallrect_in34.in
      |      ^
a.cc:233:6: error: stray '#' in program
  233 | Case #23:       : Accepted      00.00 sec       3116 KB 1392 B  5 B     sub3_smallrect_in4.in
      |      ^
a.cc:234:6: error: stray '#' in program
  234 | Case #24:       : Accepted      00.00 sec       3016 KB 2698 B  5 B     sub3_smallrect_in5.in
      |      ^
a.cc:235:6: error: stray '#' in program
  235 | Case #25:       : Runtime Error -       -       44 B    19 B    sub4_corner_in1.in
      |      ^
a.cc:236:6: error: stray '#' in program
  236 | Case #26:       -       -       -       84 B    19 B    sub4_corner_in2.in
      |      ^
a.cc:237:6: error: stray '#' in program
  237 | Case #27:       -       -       -       86 B    20 B    sub4_corner_in3.in
      |      ^
a.cc:238:6: error: stray '#' in program
  238 | Case #28:       -       -       -       53 B    19 B    sub4_corner_in4.in
      |      ^
a.cc:239:6: error: stray '#' in program
  239 | Case #29:       -       -       -       128 B   20 B    sub4_corner_in5.in
      |      ^
a.cc:240:6: error: stray '#' in program
  240 | Case #30:       -       -       -       87 B    19 B    sub5_largeeasy_in1.in
      |      ^
a.cc:241:6: error: stray '#' in program
  241 | Case #31:       -       -       -       83 B    19 B    sub5_largeeasy_in2.in
      |      ^
a.cc:242:6: error: stray '#' in program
  242 | Case #32:       -       -       -       122 B   19 B    sub5_largeeasy_in3.in
      |      ^
a.cc:243:6: error: stray '#' in program
  243 | Case #33:       -       -       -       129 B   20 B    sub5_largeeasy_in4.in
      |      ^
a.cc:244:6: error: stray '#' in program
  244 | Case #34:       -       -       -       419 B   20 B    sub6_largemedium_in1.in
      |      ^
a.cc:245:6: error: stray '#' in program
  245 | Case #35:       -       -       -       1050 B  20 B    sub6_largemedium_in2.in
      |      ^
a.cc:246:6: error: stray '#' in program
  246 | Case #36:       -       -       -       2081 B  20 B    sub6_largemedium_in3.in
      |      ^
a.cc:247:6: error: stray '#' in program
  247 | Case #37:       -       -       -       4163 B  20 B    sub6_largemedium_in4.in
      |      ^
a.cc:248:6: error: stray '#' in program
  248 | Case #38:       -       -       -       4151 B  20 B    sub6_largemedium_in5.in
      |      ^
a.cc:249:6: error: stray '#' in program
  249 | Case #39:       -       -       -       4174 B  20 B    sub6_largemedium_in6.in
      |      ^
a.cc:250:6: error: stray '#' in program
  250 | Case #40:       -       -       -       20803 B 20 B    sub7_largehard_in1.in
      |      ^
a.cc:251:6: error: stray '#' in program
  251 | Case #41:       -       -       -       41594 B 20 B    sub7_largehard_in2.in
      |      ^
a.cc:252:6: error: stray '#' in program
  252 | Case #42:       -       -       -       62346 B 20 B    sub7_largehard_in3.in
      |      ^
a.cc:253:6: error: stray '#' in program
  253 | Case #43:       -       -       -       62301 B 20 B    sub7_largehard_in4.in
      |      ^
a.cc:254:6: error: stray '#' in program
  254 | Case #44:       -       -       -       83224 B 20 B    sub7_largehard_in5.in
      |      ^
a.cc:255:6: error: stray '#' in program
  255 | Case #45:       -       -       -       83079 B 20 B    sub7_largehard_in6.in
      |      ^
a.cc:256:6: error: stray '#' in program
  256 | Case #46:       -       -       -       83104 B 20 B    sub7_largehard_in7.in
      |      ^
a.cc:257:6: error: stray '#' in program
  257 | Case #47:       -       -       -       92005 B 2 B     sub8_minmax_in1.in
      |      ^
a.cc:258:6: error: stray '#' in program
  258 | Case #48:       -       -       -       92005 B 20 B    sub8_minmax_in2.in
      |      ^
a.cc:259:6: error: stray '#' in program
  259 | Case #49:       -       -       -       91997 B 20 B    sub8_minmax_in3.in
      |      ^
a.cc:260:6: error: stray '#' in program
  260 | Case #50:       -       -       -       91997 B 18 B    sub8_minmax_in4.in
      |      ^
a.cc:264:13: error: stray '#' in program
  264 | Judge Input #25 ( in25.txt | 44 B)              Judge Output #25 ( out25.txt | 19 B)
      |             ^
a.cc:264:62: error: stray '#' in program
  264 | Judge Input #25 ( in25.txt | 44 B)              Judge Output #25 ( out25.txt | 19 B)
      |                                                              ^
a.cc:1:1: error: 'AIZU' does not name a type
    1 | AIZU ONLINE JUDGE
      | ^~~~
In file included from /usr/include/c++/14/iosfwd:42,
                 from /usr/include/c++/14/ios:40,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:109:
/usr/include/c++/14/bits/postypes.h:68:11: error: 'ptrdiff_t' does not name a type
   68 |   typedef ptrdiff_t     streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/14/bits/postypes.h:41:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/14/bits/exception_ptr.h:38,
                 from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41:
/usr/include/c++/14/new:131:26: error: declaration of 'operator new' as non-function
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:131:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/14/cwchar:44,
                 from /usr/include/c++/14/bits/postypes.h:40:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:132:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  132 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:133:26: error: declaration of 'operator new []' as non-function
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:133:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  133 | _GLIBCXX_NODISCARD void* operator ne