시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 512 163 72 24.324%

문제

축에 평행한 직사각형 N개가 평면 위에 있다. 이 직사각형들이 차지하는 전체 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 같고, 109보다 작거나 같으며, 각각의 직사각형은 x1 < x2, y1 < y2를 만족한다.

출력

첫째 줄에 주어진 직사각형 N개가 차지하는 전체 면적을 출력한다. 한 구역이 여러 개의 직사각형으로 덮어져 있는 경우에도 한 번으로 센다.

예제 입력 1

2
0 3 1 2
1 2 0 3

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6Ijc2MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IE5cdWFjMWNcdWFjMDAgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NzQgXHVjYzI4XHVjOWMwXHVkNTU4XHViMjk0IFx1YzgwNFx1Y2NiNCBcdWJhNzRcdWM4MDFcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwMCwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjOWM0IFx1YjEyNCBcdWFjMTIgJnF1b3Q7eDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4mcXVvdDtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBbeDxzdWI+MTxcL3N1Yj4seDxzdWI+MjxcL3N1Yj5dICZ0aW1lczsgW3k8c3ViPjE8XC9zdWI+LHk8c3ViPjI8XC9zdWI+XVx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDxzdXA+OTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YzczY1x1YmE3MCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCB4PHN1Yj4xPFwvc3ViPiAmbHQ7IHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiAmbHQ7IHk8c3ViPjI8XC9zdWI+XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgTlx1YWMxY1x1YWMwMCBcdWNjMjhcdWM5YzBcdWQ1NThcdWIyOTQgXHVjODA0XHVjY2I0IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMzZlXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIzYzQgXHVkNTVjIFx1YmM4OFx1YzczY1x1Yjg1YyBcdWMxM2NcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzYyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlY3RhbmdsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBOIGF4aXMtcGFyYWxsZWwgcmVjdGFuZ2xlcyBpbiB0aGUgcGxhbmUuIENhbGN1bGF0ZSB0aGUgdG90YWwgYXJlYSB0aGV5IGNvdmVyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAyMDAsIDAwMCkuIE4gbGluZXMgdGhlbiBmb2xsb3csIGVhY2ggd2l0aCBmb3VyIHNwYWNlLXNlcGFyYXRlZCB2YWx1ZXMgJmxkcXVvO3g8c3ViPjE8XC9zdWI+IHg8c3ViPjI8XC9zdWI+IHk8c3ViPjE8XC9zdWI+IHk8c3ViPjI8XC9zdWI+JnJkcXVvOyBkZW5vdGluZyB0aGUgcmVjdGFuZ2xlIFt4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj5dJnRpbWVzO1t5PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj5dLiBFYWNoIG9mIHRoZSB2YWx1ZXMgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4gYXJlIGludGVnZXJzIGJldHdlZW4gMCBhbmQgMTA8c3VwPjk8XC9zdXA+LCBpbmNsdXNpdmUsIGFuZCBmb3IgYSBnaXZlbiByZWN0YW5nbGUgeDxzdWI+MTxcL3N1Yj4gJmx0OyB4PHN1Yj4yPFwvc3ViPiBhbmQgeTxzdWI+MTxcL3N1Yj4gJmx0OyB5PHN1Yj4yPFwvc3ViPiBhbHdheXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSB0b3RhbCBhcmVhIGNvdmVyZWQgYnkgdGhlIGdpdmVuIE4gcmVjdGFuZ2xlcy4gQW55IHJlZ2lvbiBjb3ZlcmVkIGJ5IG11bHRpcGxlIHJlY3RhbmdsZXMgc2hvdWxkIG9ubHkgYmUgY291bnRlZCBvbmNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==