Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Crease Painting CodeChef Solution
Problem -Crease Painting CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Crease Painting CodeChef Solution in C++14
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <map>
#include <cassert>
#define mod 1000000007
#define PHI 1000000006
#define ull unsigned long long
#define ll long long int
#define pii pair<int,int>
#define pb(x) push_back(x)
#define F(i,a,n) for(i=(a);i<(n);++i)
#define FD(i,a,n) for(i=(a);i>=(n);--i)
#define FE(it,x) for(it=x.begin();it!=x.end();++it)
#define V(x) vector<x>
#define S(x) scanf("%d",&x)
#define S1(x) scanf("%llu",&x)
#define MAX 50009
#define NIL 0
#define INF (1<<28)
#define MAXNODES 50009
using namespace std;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
ll startx[1002];
ll endx[1002];
ll starty[1002];
ll endy[1002];
void intersect(ll sx1,ll sy1,ll ex1,ll ey1,ll sx2,ll sy2,ll ex2,ll ey2, vector<pair<ll,ll> >* segments)
{
if(sx2==ex2)
{
if(sx1!=sx2)
return;
ll sy3=max(min(sy1,ey1),min(sy2,ey2));
ll ey3=min(max(sy1,ey1),max(sy2,ey2));
if(sy3>ey3)
return;
segments->push_back(make_pair(sy3,ey3));
return;
}
if(sy2==ey2)
{
if(sy2>=min(sy1,ey1) && sy2<=max(sy1,ey1) && min(sx2,ex2)<=sx1 && max(sx2,ex2)>=sx1)
segments->push_back(make_pair(sy2,sy2));
return;
}
}
map<pair<int,int>,bool> hashed;
int main()
{
int N;
scanf("%d",&N);
ll cx=0;
ll cy=0;
ll answer=0;
startx[0]=endx[0]=starty[0]=endy[0]=0;
for(int i=1;i<=N;i++)
{
char dir[3];
ll steps;
int id;
scanf("%s",&dir);
scanf("%lld",&steps);
if(dir[0]=='R')
id=0;
if(dir[0]=='L')
id=1;
if(dir[0]=='U')
id=2;
if(dir[0]=='D')
id=3;
startx[i]=cx+dx[id];
starty[i]=cy+dy[id];
endx[i]=cx+dx[id]*steps;
endy[i]=cy+dy[id]*steps;
cx=endx[i];
cy=endy[i];
vector<pair<ll,ll> > segments;
for(int j=0;j<i;j++)
{
if(startx[i]==endx[i])
intersect(startx[i],starty[i],endx[i],endy[i],startx[j],starty[j],endx[j],endy[j],&segments);
else
intersect(starty[i],startx[i],endy[i],endx[i],starty[j],startx[j],endy[j],endx[j],&segments);
}
sort(segments.begin(),segments.end());
ll st=(startx[i]==endx[i]?min(starty[i],endy[i]):min(startx[i],endx[i]));
ll en=(startx[i]==endx[i]?max(starty[i],endy[i]):max(startx[i],endx[i]));
ll currocc=en-st+1;
for(int j=0;j<segments.size();j++)
{
currocc-=max(0ll,(segments[j].second-max(st,segments[j].first))+1);
st=max(st,segments[j].second+1);
}
answer+=currocc;
printf("%lld\n",currocc);
}
}Crease Painting CodeChef Solution in JAVA
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni();
int[][] pa = new int[n][];
for(int i = 0;i < n;i++){
int c = nc();
int d = ni();
pa[i] = new int[]{c, d};
}
long x = 0, y = 0;
long[][] co = new long[n][];
for(int i = 0;i < n;i++){
int c = pa[i][0], d = pa[i][1];
if(c == 'U'){
co[i] = new long[]{x, y, x+1, y+1+d};
y += d;
}else if(c == 'D'){
co[i] = new long[]{x, y-d, x+1, y+1};
y -= d;
}else if(c == 'R'){
co[i] = new long[]{x, y, x+1+d, y+1};
x += d;
}else{
co[i] = new long[]{x-d, y, x+1, y+1};
x -= d;
}
}
long[] shx = new long[2*n];
for(int i = 0;i < n;i++){
shx[2*i] = co[i][0];
shx[2*i+1] = co[i][2];
}
Object[] resx = shrink(shx);
int[] shedx = (int[])resx[0];
long[] ix = (long[])resx[1];
long[] shy = new long[2*n];
for(int i = 0;i < n;i++){
shy[2*i] = co[i][1];
shy[2*i+1] = co[i][3];
}
Object[] resy = shrink(shy);
int[] shedy = (int[])resy[0];
long[] iy = (long[])resy[1];
boolean[][] F = new boolean[ix.length][iy.length];
for(int i = 0;i < n;i++){
long S = 0;
for(int j = shedx[2*i];j < shedx[2*i+1];j++){
for(int k = shedy[2*i];k < shedy[2*i+1];k++){
if(!F[j][k]){
F[j][k] = true;
S += ix[j] * iy[k];
}
}
}
if(i == 0)S--;
out.println(S);
}
}
public static Object[] shrink(final long[] a)
{
int n = a.length;
Integer[] b = new Integer[n];
for(int i = 0;i < n;i++)b[i] = i;
Arrays.sort(b, new Comparator<Integer>(){
public int compare(Integer x, Integer y){
return Long.signum(a[x] - a[y]);
}
});
int[] ret = new int[n];
long[] interval = new long[n];
int p = 0;
for(int i = 0;i < n;i++){
if(i > 0 && a[b[i]] > a[b[i-1]]){
interval[p] = a[b[i]]-a[b[i-1]];
p++;
}
ret[b[i]] = p;
}
return new Object[]{ret, Arrays.copyOf(interval, p)};
}
static char nc()
{
try {
int b;
while((b = is.read()) != -1 && (b == ' ' || b == '\r' || b == '\n'));
if(b == -1)return 0;
return (char)b;
} catch (IOException e) {
}
return 0;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
static boolean eof()
{
try {
is.mark(1000);
int b;
while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
is.reset();
return b == -1;
} catch (IOException e) {
return true;
}
}
static int ni()
{
try {
int num = 0;
boolean minus = false;
while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
if(num == '-'){
num = 0;
minus = true;
}else{
num -= '0';
}
while(true){
int b = is.read();
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}
static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}Crease Painting CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
"sort"
)
func main() {
reader := bufio.NewReader(os.Stdin)
n := readNum(reader)
S := make([]string, n)
for i := 0; i < n; i++ {
S[i] = readString(reader)
}
res := solve(n, S)
var buf bytes.Buffer
for i := 0; i < n; i++ {
buf.WriteString(fmt.Sprintf("%d\n", res[i]))
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(n int, commands []string) []int {
ans := make([]int, n)
var x, y int64
strips := make([]Stripe, n+1)
strips[0] = Stripe{0, 0, 0, 0}
for i := 0; i < n; i++ {
cmd := parseCommand(commands[i])
if cmd.dir == 'L' {
strips[i+1] = NewStripe(x-1, y, x-cmd.dis, y)
x -= cmd.dis
} else if cmd.dir == 'R' {
strips[i+1] = NewStripe(x+1, y, x+cmd.dis, y)
x += cmd.dis
} else if cmd.dir == 'U' {
strips[i+1] = NewStripe(x, y+1, x, y+cmd.dis)
y += cmd.dis
} else {
strips[i+1] = NewStripe(x, y-1, x, y-cmd.dis)
y -= cmd.dis
}
var horizontal bool
if cmd.dir == 'L' || cmd.dir == 'R' {
horizontal = true
}
var ps []Point
for j := 0; j <= i; j++ {
ok, intersection := intersect(strips[i+1], strips[j])
if ok {
if horizontal {
ps = append(ps, Point{intersection.x1 - strips[i].x1, false})
ps = append(ps, Point{intersection.x2 - strips[i].x1 + 1, true})
} else {
ps = append(ps, Point{intersection.y1 - strips[i].y1, false})
ps = append(ps, Point{intersection.y2 - strips[i].y1 + 1, true})
}
}
}
sort.Sort(Points(ps))
var covered int
var last int64
var painted = cmd.dis
for j := 0; j < len(ps); j++ {
p := ps[j]
if covered > 0 {
painted -= p.coord - last
}
if p.begin {
covered--
} else {
covered++
}
last = p.coord
}
ans[i] = int(painted)
}
return ans
}
type Stripe struct {
x1, y1, x2, y2 int64
}
func NewStripe(x1, y1, x2, y2 int64) Stripe {
return Stripe{min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)}
}
func intersect(a, b Stripe) (bool, Stripe) {
x1 := max(a.x1, b.x1)
y1 := max(a.y1, b.y1)
x2 := min(a.x2, b.x2)
y2 := min(a.y2, b.y2)
if x1 > x2 || y1 > y2 {
return false, Stripe{}
}
return true, Stripe{x1, y1, x2, y2}
}
type Point struct {
coord int64
begin bool
}
func (this Point) Less(that Point) bool {
if this.coord != that.coord {
return this.coord < that.coord
}
if this.begin != that.begin {
return !this.begin
}
return false
}
type Points []Point
func (this Points) Len() int {
return len(this)
}
func (this Points) Less(i, j int) bool {
return this[i].Less(this[j])
}
func (this Points) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}
func min(a, b int64) int64 {
if a <= b {
return a
}
return b
}
func max(a, b int64) int64 {
if a >= b {
return a
}
return b
}
type Command struct {
dir byte
dis int64
}
func parseCommand(s string) *Command {
dir := s[0]
var dis int
readInt([]byte(s), 2, &dis)
return &Command{dir, int64(dis)}
}Crease Painting CodeChef Solution Review:
In our experience, we suggest you solve this Crease Painting CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Crease Painting CodeChef Solution.
Conclusion:
I hope this Crease Painting CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
